SMART-LAB
Новый дизайн
Мы делаем деньги на бирже
Информация
Блог им. _sk_
Re: Тестик. Наивный Теорвер.
- 04 января 2017, 07:55
- |
В настоящее время компьютеры могут многое. В том числе они помогают проверить, правильно ли мы рассуждаем с использованием математических методов, не закралась ли где-то ошибка. В посте Тестик. Наивный Теорвер предлагалось решить задачу про робота, который ходит по квадратному листу книги.
Поскольку времени подумать над задачкой всем заинтересовавшимся было достаточно, пора разобраться с тем, каков же правильный ответ. Ниже приводится решение методом Монте-Карло.
Применим java. Код программы, которую можно написать за 10-15 минут, приведён ниже. Идея проста: моделируем ходы робота по листу и регистрируем, сколько раз он вышел за край страницы 108, а сколько раз перешёл на страницу 107, исходя из координат его текущего положения. После многократного моделирования можно определить частоту попадания на 107-ю страницу, которая по закону больших чисел будет приближаться к вероятности события при увеличении числа независимых экспериментов.
Запускаем программу, через некоторое время видим ответ: после 100 млн. итераций частота попадания на 107-ю страницу равна 0.25003493.
Мы знаем, что метод Монте-Карло даёт погрешности, так что можно предположить, что ответ задачи — это 0.25.
А вот теперь можно уже, зная ответ, попытаться доказать его математически. Пусть существует какая-то траектория, двигаясь по которой робот приходит на страницу 107. Если повернуть эту траекторию на 90 градусов, 180 градусов или 270 градусов, то робот по повёрнутой траектории выйдет за пределы 108-й страницы. Тут существенно используется факт того, что страница квадратная, а робот стартует из центра. Если же изначально взять траекторию, приводящую к выходу за границу, то её всегда можно повернуть так, чтобы в результате робот пришёл на 107-ю страницу. Итого имеем разбиение всех траекторий на 4 класса: выход на 107-ю страницу, выход за верхний край, выход за нижний край и выход за боковой край 108-й страницы. В каждом классе одинаковое число траекторий. Для каждой траектории одного класса имеются по одной траектории из каждого из оставшихся 3-х классов с той же вероятностью движения по ней. Поскольку выход куда-нибудь происходит наверняка, то вероятности каждого из классов одинаковы, так что ответом задачи будет 1/4 = 0.25.
А можно просто поиграться с программой. Например, узнать, что будет, если листы книги не квадратные и/или робот стартует не из центра.
Чаще используйте метод Монте-Карло! Он и в трейдинге тоже полезен.
Большая просьба, особенно к А.Г.))), не писать сразу решение)))
Поскольку времени подумать над задачкой всем заинтересовавшимся было достаточно, пора разобраться с тем, каков же правильный ответ. Ниже приводится решение методом Монте-Карло.
Применим java. Код программы, которую можно написать за 10-15 минут, приведён ниже. Идея проста: моделируем ходы робота по листу и регистрируем, сколько раз он вышел за край страницы 108, а сколько раз перешёл на страницу 107, исходя из координат его текущего положения. После многократного моделирования можно определить частоту попадания на 107-ю страницу, которая по закону больших чисел будет приближаться к вероятности события при увеличении числа независимых экспериментов.
package com.company.experiments;
import java.util.Random;
class Walker {
/**
* Датчик случайных чисел.
*/
final Random rnd = new Random(1L);
/**
* Количество попаданий на 107-ю страницу.
*/
int successes = 0;
/**
* Количество выходов за край страницы.
*/
int failures = 0;
public static void main(final String[] args) {
final Walker walker = new Walker();
walker.test(100_000_000);
System.out.println(walker.getFrequency());
}
void test(final int iterations) {
for (int i = 0; i < iterations; i++) {
walk();
}
}
void walk() {
int x = 5;
int y = 5;
while (true) {
// Определить направление движения и сделать шаг
final int d = rnd.nextInt(4);
if (d == 0) {
x++;
} else if (d == 1) {
x--;
} else if (d == 2) {
y++;
} else if (d == 3) {
y--;
}
// Проверить выход за пределы 108-й страницы
if (y == -1 || y == 11 || x == 11) {
failures++;
return;
}
// Проверить попадание на 107-ю страницу
if (x == -1) {
successes++;
return;
}
}
}
double getFrequency() {
return (double) successes / (successes + failures);
}
}
Запускаем программу, через некоторое время видим ответ: после 100 млн. итераций частота попадания на 107-ю страницу равна 0.25003493.
Мы знаем, что метод Монте-Карло даёт погрешности, так что можно предположить, что ответ задачи — это 0.25.
А вот теперь можно уже, зная ответ, попытаться доказать его математически. Пусть существует какая-то траектория, двигаясь по которой робот приходит на страницу 107. Если повернуть эту траекторию на 90 градусов, 180 градусов или 270 градусов, то робот по повёрнутой траектории выйдет за пределы 108-й страницы. Тут существенно используется факт того, что страница квадратная, а робот стартует из центра. Если же изначально взять траекторию, приводящую к выходу за границу, то её всегда можно повернуть так, чтобы в результате робот пришёл на 107-ю страницу. Итого имеем разбиение всех траекторий на 4 класса: выход на 107-ю страницу, выход за верхний край, выход за нижний край и выход за боковой край 108-й страницы. В каждом классе одинаковое число траекторий. Для каждой траектории одного класса имеются по одной траектории из каждого из оставшихся 3-х классов с той же вероятностью движения по ней. Поскольку выход куда-нибудь происходит наверняка, то вероятности каждого из классов одинаковы, так что ответом задачи будет 1/4 = 0.25.
А можно просто поиграться с программой. Например, узнать, что будет, если листы книги не квадратные и/или робот стартует не из центра.
Чаще используйте метод Монте-Карло! Он и в трейдинге тоже полезен.
теги блога _sk_
- CLJ0
- Eu
- LUA
- qlua
- quik
- Quik Lua
- RSI
- Si
- SR
- адаптивность
- алгоритмическая торговля
- алготрейдинг
- байка
- биржа
- веселье
- восстановление экономики
- выигрыш
- гарантийное обеспечение
- гипотезы
- головоломка
- дедолларизация
- Динамика
- Доллар рубль
- ДУ
- закономерности
- игры
- Изменчивость рынка
- индикатор
- индикаторы
- Книги
- комиссия биржи
- коронавирус
- котирование
- крупная сделка
- крупные сделки
- кукл
- Масштабирование
- математика
- математические модели
- Модели рынка
- монте-карло
- МосБиржа
- Московская биржа
- мошенники
- Нейросети
- Нефть
- обезличенные сделки
- обороты торгов
- объемы торгов
- ответы
- паттерны
- позиции
- поставочные фьючерсы
- Программирование
- профессионализм
- профессионалы
- разработка торговых систем
- Рэнкинг управляющих
- Сбербанк
- сделка
- софт для трейдинга
- спред
- срочный рынок
- стабильность
- теория вероятностей
- теория игр
- тестирование
- тестирование на истории
- Тестирование стратегий
- тики
- Торговые идеи
- торговые роботы
- Торговые роботы для Quik
- торговые сигналы
- торговые системы
- трейдинг
- Управление капиталом
- участники рынка
- ФЬЮЧЕРСЫ
- хаос
- Чак Норрис
- эквити
- юмор
У меня логически получилось 1/3
Если в условии
y == -1 || y == 11 || x == 11
убрать проверку x == 11, а оставить только
y == -1 || y == 11
то получится ответ
0.26120199
на 100 млн. итераций.
Понятно, что отодвигание боковой границы добавляет шансов вернуться назад и перейти на 107-ю страницу, но это влияние мало, т.к. исходный край уже довольно далеко.
Так что 1/3, по-видимому, неверный ответ.
Вообще, если симметрия в этой задаче нарушается, то, скорее всего, сразу же ответы перестают быть простыми и наивными.
y == -1 || y == 11 || x == 1011
1/3 похоже не правильный ответ, если без «x ==» всего 0,26
Соответственно, попасть на верх или низ 0,346574…
Сейчас стало интересно среднее число ходов до падения с края узнать.
42,3 в исходной задаче, и в задаче без края — 46,3 до 107 стр. и 60,3 до верха-низа.
но без программы это было не так понятно. видать я не обратил внимание на квадратность.
а как это пересекается с графиками.?..
я рассуждал так, у робота 4 направления, они равновероятны, значит вероятность 1 направления 25%
вот и всё
Нет ли у него навязчивых тенденций?
Собирался ответить во вчерашнем топике, но здесь уместнее, поскольку был задан еще один хороший вопрос, типа, а какое отношение все это имеет к рынку?
Очень хорошая задача, просто показательная.
Попробую определить свое отношение к ней. Правда, в виде вопросов.
Нужен ли теорвер для решения этой задачи?
Почему я однозначно понимаю условия, а кто-то – нет?
Почему у кого-то возникает желание подменить задачу другой? Я не против развитого воображения, но часто нужен вполне конкретный ответ.
Хорошая аналогия с задачей устройства рынка.
В рынке тоже есть очень хорошие вопросы, их даже много. И ответы тоже есть.
И у многих сложных вопросов есть простые ответы, надо только ими задаться.
Почему случайное блуждание и теорвер?
Разве нет сомнений в их полноценности в рынке? Как и многого другого.
Если есть сомнения, то почему не посмотреть другие идеи и не воспользоваться другим инструментарием?
Или удобнее использовать теорвер или матстатистику или еще что-то только потому, что вы хорошо ими владеете и успешно использовали их для решения каких-то других прикладных задач?
Отвечать или искать ответы на все эти вопросы каждый должен сам.
А первый хороший вопрос – о вероятности заблудиться на странице и не свалиться. Вот решение, которое может устроить многих. Можно найти в интернете в более общем виде.
11 шагов в одном и том же направлении гарантированно сваливают робота, откуда бы с начальной страницы он ни начинал. Вероятность пройти таким редким маршрутом p=(1/4)**11, кто-то даже примерялся. Вероятность свалиться на самом деле выше, но не будем мелочиться. Вероятность остаться на странице после 11 произвольных шагов меньше, чем q=1-p. Близко к 1, но все-таки меньше. Делаем N движений по 11 шагов, вероятность остаться на странице уменьшится и не превысит q**N. Школьная геометрическая прогрессия. Предел – 0 при стремлении N к бесконечности. Вероятность – 0.
Чего здесь больше: теорвера, матанализа или школьных знаний со здравым смыслом?
Касательно рынка, я полагаю, что изначально задача выделения границ, в которых заключена цена, нетривиальная: там изначально всё «кривое». Если у Вас действительно получилось применить математический аппарат, то это реально круто! И с научной точки зрения это интересно. Из Вашего блога я пока не смог составить представления, как именно.
У меня когда-то была подсказка одного гуру:«рынок нелинеен». Хорошая подсказка оказалась.
А Монте-Карло я раньше использовал. И исследовательских индикаторов у меня около сотни.
Можно еще схлопнуть страницу в ноль и считать комбинаторно траектории постепенно добавляя ячейки по периметру. Таким образом вывести соотношение и записать предел.
Я только не совсем понял, вы не согласны с ответом 25% или согласны?
В исходной теме вы уклончиво сказали что это другая задача (хотя по мне так та же самая), и мне показалось что ответ у вас тоже другой.
Обратили внимание, что тема случайного блуждания с «математическими» алгоритмами извлечения из него прибыли, да и вообще любая тема с «математикой» пользуется успехом на SL? Месяц-два назад была пара таких постов с очевидными ошибками и оценку они получили высокую.
Гусев Владимир Павлович со свойственной ему искренностью сказал бы:«Какое случайное блуждание, какой теорвер, здесь не казино и мы не в карты или рулетку играем и не монетку бросаем».
Я человек деликатный и прямо так сказать не могу, но попробовать зародить сомнение я обязан.
Сам теорвер конечно не обеспечивает преимущества на рынке, но позволяет (разумеется, после некоторого осмысления базовых концепций) более адекватно оценивать выдвигаемые гипотезы о его свойствах.
К примеру, тоже самое монте-карло при корректной методологии позволяет выявить эффект оверкурвфиттинга модели путём разрушения автокорреляционных связей исходного временного ряда. Конечно, тут тоже нужно чётко понимать границы применимости.
Господин Гусев намеренно или неосознанно подобрал в том видео несколько низколиквидных сильнотрендовых активов и делает скоропалительные и ложные, на мой взгляд, выводы.
Если взять, например, кросс EURUSD, то после нормировки на локальную волатильность распределение приращений становится почти идеально Гауссовым без значимых автокорреляций. Это тот самый сильноэффективный рынок из учебников. И заработать на нем чертовски сложно. Но чтобы это осознать, приходится порой применять и матстат и теорвер.
Для построений типа ренко-каги не пробовали подобное?
Еще интересно как это отрабатывает на самых ликвидных рынках? например фьючи на проц.ставку eurodollar, на десятилетние ноты, SnP500, nasdaq, нефть, золото, трежурис и бунды, спот eurusd и usdjpy
Изредка отслеживаю поведение акций и фьючерсов в большом диапазоне, но глаз уже на автомате цепляется за известные мне формы и на других графиках.
Вот мой сравнительно свежий комментарий, некоторые моменты относительно моего выбора.
smart-lab.ru/blog/371377.php#comment6659874
Правда, я не понимаю, причем тут метод Монте Карло? Разве под «монте-карло» понимается честный рандом, не математический? Программный рандом обычно честный, там используется температура проца и пр.
Монте-карло хорошая вещь. Но тут из пушки по воробьям, конечно. И так понятно, что финальные состояния «упасть сверху страницы», «упасть в сторону», «упасть снизу страницы», «перейти на 107» равновероятны.
С другой стороны, сформулируем задачу «Какова вероятность упасть, ни разу не подойдя к границе страницы 107?» (без разницы, пересечь, или просто подойти к границе), и получаем задачу чуть сложнее, для решения которой придется подумать, а вот монте-карло решит запросто)
А по сформулированной задаче, которая от исходной отличается только тем, что «107» на клетку ближе, чем остальные границы, можно оценить вероятность упасть как 10/21.