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.
А можно просто поиграться с программой. Например, узнать, что будет, если листы книги не квадратные и/или робот стартует не из центра.
Чаще используйте метод Монте-Карло! Он и в трейдинге тоже полезен.
Стратегия у них одна: когда люди вышли по 154, срубив куш от последующих событий, то им надо отобрать эту прибыль — выпустили допку по 8 руб за акцию, продают по 51 в надежде, что кто вышел по 154 сно...
Инфографика по ОФЗ 26238 Облигация ОФЗ 26238 (SU26238RMFS4) стоит сейчас 593,46 руб или 59,34% от номинала. Облигация будет полностью погашена по номиналу 15.05.2041 г. Текущая доходность облигации к ...
Nordstream, так-то +20% г/г див. Кто знает, может видим перед собой будущего див аристократа
Аксинья, ну пусть хребет воткнет)))
Али Картоев, а вот когда начнется коррекция рынка, то эта какаха полетит вместе со всеми))
Компания интересная, но неэффективная от слова совсем
10:35
ALB, это наверное на второй выкуп? Первый то выкуп ещё в марте объявляли, я про тот писал.
10:30
Вредный инвестор,
КАКИЕ могут быть дела в бумаге которая ПАДАЕТ,
ВСЕ рост ее закончился. Теперь только через ГОД.
Упадет и будет ГОД болтаться (.
И упадет то еще не скоро...
Так что сове...
С видом на Кремль, очень удобно, пешком до работы 5 минут и на «троичку» тратиться не надо
Светлана родилась в сентябре 1973 года в Москве. Её бизнес-карьера развивалась достаточно бурно, уже в 9...
10:22
Вася Баффет, да мы про другое. Про МТС Банк, человек не понял, как у них доля сократилась, а акции они не продавали. Так они допку сделали и продали её.
10:22
Alex Petrov, и женщин резиновых сейчас делают за 20 минут специально для тех кто купил искуственные алмазы.
У меня логически получилось 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.