04 января 2017, 07:55
Re: Тестик. Наивный Теорвер.
В настоящее время компьютеры могут многое. В том числе они помогают проверить, правильно ли мы рассуждаем с использованием математических методов, не закралась ли где-то ошибка. В посте Тестик. Наивный Теорвер предлагалось решить задачу про робота, который ходит по квадратному листу книги.
Поскольку времени подумать над задачкой всем заинтересовавшимся было достаточно, пора разобраться с тем, каков же правильный ответ. Ниже приводится решение методом Монте-Карло.
Применим 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.
А можно просто поиграться с программой. Например, узнать, что будет, если листы книги не квадратные и/или робот стартует не из центра.
Чаще используйте метод Монте-Карло! Он и в трейдинге тоже полезен.
Потеряев А.А., ну ты отнеси налог 13% с дивов
16:57
Каво, бля?!?????
16:57
Коммунизму быть!, ну у Газпрома щас не просто такая цена. Это его цена за жадность, когда были деньги не делился, сейчас тем более никто лезьт не хочет
"НоваБев Групп" Проведение заседания совета директоров и его повестка дня 2. Содержание сообщения
2.1. Дата принятия председателем совета директоров (наблюдательного совета) эмитента решени...
16:53
⚡16 раз в 2024 не состоялись аукционы ОФЗ, рекорд за 9 лет вместе взятых В этом году 16 раз признали аукционы не состоявшимися, для сравнения, за все предыдущие 9 лет не состоялось 13 аукционов.
...
16.12.2024, 01:33
На счетах российских брокеров оказалось более 2 трлн рублей из разных юрисдикций.
На фоне снижения российского фондового рынка активы нерезидентов на счетах российских брокеро...
Сергей Кузьмин, Тогда нам с вами не о чем разговаривать, если у них маржинальность выше чем у сбера раз в 5 по вашим словам. Т.е. они должны каждый год удваиваться, а они уполовиниваются, вот ведь ...
🏦 Т-Технологии продолжают радовать результатами! Сегодня стало известно, что за 11 месяцев банк увеличил чистую прибыль аж на 41%, что является лучшим результатом во всем секторе.✨ И это в очередной р...
Антон Михеев, это ты мне пишешь, а я лишь отвечаю из вежливости на твою ахинею и попытки перекладывать диагнозы с больной головы на здоровую.
Heinrich von Baur, нету у меня Яндекса, я просто выбираю акции, захожу на ветку чего-нибудь интересного почитать, а тут два болвана ты и заяц какой-то бред про капу 10 трлн пишут, ещё и агрызаются,...
У меня логически получилось 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.