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.
А можно просто поиграться с программой. Например, узнать, что будет, если листы книги не квадратные и/или робот стартует не из центра.
Чаще используйте метод Монте-Карло! Он и в трейдинге тоже полезен.
Тимур,
Там остаются, в итоге, тока султанчики — которые и банкуют парадом
19:24
igorwolf, — 22кг., скинул — в экстремальных условиях за 3 недели!
rutube.ru/video/7f3eb7d9c8059eee38957a8d2543e813/?r=a
Жаль что такой умный, правильный и талантливый человек как Стивен Сигал поздно понял что родился и прожил бОльшую часть своей жизни, мягко говоря, не среди своих...
19:16
Metzger,
Новый министр энергетики в новой администрации Трампа: Крис Райт, нефтяник и страстный сторонник использования ископаемого топлива.
вот и все. привет нефть по 30. больше 7к не увидим уже...
Диктатор, ты по графику это видишь? Или есть еще какие-то факторы? Новости никакие не запускают?
khornickjaadle, сварено уже 280 км из 770 км это данные на конец второго полугодия 2024, но последние 180 км они два года строили. Очевидно морозят стройку.
Лесенкой, денег нет, а люди это новая нефть. Будет большой.
Наталия Суханова,
Кончился пятый день ДЕКАМЕРОНА, начинается шестой.
В день правления Элиссы предлагаются вниманию рассказы о том, как люди, уязвленные чьей-либо шуткой, платили тем же или ...
00597681,
Так певуны за 16 млн вообще никому не нужны
даже бесплатно в бывшие советские их не приглашают.
Pinkin, душу греют Ваши зелёные картинки
У меня логически получилось 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.