Блог им. _sk_

Re: Тестик. Наивный Теорвер.

    • 04 января 2017, 07:55
    • |
    • _sk_
  • Еще
В настоящее время компьютеры могут многое. В том числе они помогают проверить, правильно ли мы рассуждаем с использованием математических методов, не закралась ли где-то ошибка. В посте Тестик. Наивный Теорвер предлагалось решить задачу про робота, который ходит по квадратному листу книги.

Большая просьба, особенно к А.Г.))), не писать сразу решение)))

Поскольку времени подумать над задачкой всем заинтересовавшимся было достаточно, пора разобраться с тем, каков же правильный ответ. Ниже приводится решение методом Монте-Карло.


Применим 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.

А можно просто поиграться с программой. Например, узнать, что будет, если листы книги не квадратные и/или робот стартует не из центра.

Чаще используйте метод Монте-Карло! Он и в трейдинге тоже полезен.
★3
30 комментариев
Можете посчитать то же самое с условием, что роботу разрешено «перелистывать страницы»? т.е. поле страницы имеет бесконечный боковой размер (можно ограничиться, например 1000 клеточек).
У меня логически получилось 1/3
avatar
finstrateg, не уверен, что правильно Вас понял.

Если в условии
y == -1 || y == 11 || x == 11
убрать проверку x == 11, а оставить только
y == -1 || y == 11
то получится ответ
0.26120199
на 100 млн. итераций.

Понятно, что отодвигание боковой границы добавляет шансов вернуться назад и перейти на 107-ю страницу, но это влияние мало, т.к. исходный край уже довольно далеко.

Так что 1/3, по-видимому, неверный ответ.

Вообще, если симметрия в этой задаче нарушается, то, скорее всего, сразу же ответы перестают быть простыми и наивными.
avatar
_sk_, да, надо условие так записать, добавив 1000 клеточек на случай если робот заблудится в бесконечности )))
y == -1 || y == 11 || x == 1011
1/3 похоже не правильный ответ, если без «x ==» всего 0,26
avatar
finstrateg, если вернуться в условия предыдущей задачи, что выход наступает на 6-й клетке в одну из сторон, но добавить ваше условие, что в сторону увеличения страниц можно блуждать без окончания игры, то вероятность попасть на 107-ю страницу раньше, чем свалиться с верха или низа, равна 0,306853 …
Соответственно, попасть на верх или низ 0,346574…
avatar
MS, странно, у _sk_ получится ответ 0.26120199 ))) — кто-то ошибся
avatar
finstrateg, он. С техникой не поспоришь. Я сделал лишь грубую прикидку формулами. Можно было точнее, но трудоёмко.
Сейчас стало интересно среднее число ходов до падения с края узнать.
42,3 в исходной задаче, и в задаче без края — 46,3 до 107 стр. и 60,3 до верха-низа.

avatar
действительно, если страница квадратная, и нам нужен 1 из 4х исходов, с равными вероятностями...
но без программы это было не так понятно. видать я не обратил внимание на квадратность.

а как это пересекается с графиками.?..
avatar

я рассуждал так, у робота 4 направления, они равновероятны, значит вероятность 1 направления 25% 

вот и всё

avatar
Это не спортивное поведение)
avatar
Но метод хороший, часто проще численно прикинуть через ГСЧ чем аналитечески решать
avatar
Остается аыяснить, насколько гсч действительно генерит случайные числа)
Нет ли у него навязчивых тенденций?
avatar
Йоганн, для этой задачи это не так уж и важно, главное сбрасывать генератор при новом прогоне
avatar
Йоганн, для такой задачи, как эта, всё ок, поскольку генератор (a linear congruential formula; see Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1) проходит набор базовых тестов на равномерное распределение.
avatar
wrmngr, 

Собирался ответить во вчерашнем топике, но здесь уместнее, поскольку был задан еще один хороший вопрос, типа, а какое отношение все это имеет к рынку?

Очень хорошая задача, просто показательная.

Попробую определить свое отношение к ней. Правда, в виде вопросов.

Нужен ли теорвер для решения этой задачи?

Почему я однозначно понимаю условия, а кто-то – нет?

Почему у кого-то возникает желание подменить задачу другой? Я не против развитого воображения, но часто нужен вполне конкретный ответ.

Хорошая аналогия с задачей устройства рынка.

В рынке тоже есть очень хорошие вопросы, их даже много. И ответы тоже есть.

И у многих сложных вопросов есть простые ответы, надо только ими задаться.

Почему случайное блуждание и теорвер?

Разве нет сомнений в их полноценности в рынке? Как и многого другого.

Если есть сомнения, то почему не посмотреть другие идеи и не воспользоваться другим инструментарием?

Или удобнее использовать теорвер или матстатистику или еще что-то только потому, что вы хорошо ими владеете и успешно  использовали их для решения каких-то других прикладных задач?

 Отвечать или искать ответы на все эти вопросы каждый должен сам.

 

А первый хороший вопрос – о вероятности заблудиться на странице и не свалиться. Вот решение, которое может устроить многих. Можно найти в интернете в более общем виде.

11 шагов в одном и том же направлении гарантированно сваливают робота, откуда бы с начальной  страницы он ни начинал. Вероятность пройти таким редким маршрутом  p=(1/4)**11, кто-то даже примерялся. Вероятность свалиться на самом деле выше, но не будем мелочиться. Вероятность остаться  на странице после 11 произвольных шагов меньше, чем q=1-p. Близко к 1, но все-таки меньше. Делаем N движений по 11 шагов, вероятность остаться на странице уменьшится и не превысит q**N. Школьная геометрическая прогрессия. Предел – 0 при стремлении N к бесконечности. Вероятность – 0.

Чего здесь больше: теорвера, матанализа или школьных знаний со здравым смыслом?

Борис Гудылин, конкретно эта задача показательна тем, что её можно решить элементарными методами, так что её можно отнести к «наивному терверу». Но как только мы слегка отступаем от исходной постановки задачи в любую сторону (неквадратный лист, не из центра выходим, неравновероятное движение по 4-м направлениям), так сразу же всё заметно усложняется. Моделирование даёт ответ с некоторой точностью, а аналитическое решение уже нетривиально.

Касательно рынка, я полагаю, что изначально задача выделения границ, в которых заключена цена, нетривиальная: там изначально всё «кривое». Если у Вас действительно получилось применить математический аппарат, то это реально круто! И с научной точки зрения это интересно. Из Вашего блога я пока не смог составить представления, как именно.
avatar
_sk_, я старался не раскрывать ключевые моменты. Может, что-то будет яснее, если посмотрите мои последние комментарии к чужим постам. Старые уже недоступны.
У меня когда-то была подсказка одного гуру:«рынок нелинеен». Хорошая подсказка оказалась. 

А Монте-Карло я раньше использовал. И исследовательских индикаторов у меня около сотни. 
Борис Гудылин, согласен. можно идти разными путями и решить первый вопрос о вероятности заблудится на странице. 
Можно еще схлопнуть страницу в ноль и считать комбинаторно траектории постепенно добавляя ячейки по периметру. Таким образом вывести соотношение и записать предел. 

Я только не совсем понял, вы не согласны с ответом 25% или согласны?

avatar
wrmngr, согласен. А в выборе пути я себя не ограничиваю.
Борис Гудылин, ок.
В исходной теме вы уклончиво сказали что это другая задача (хотя по мне так та же самая), и мне показалось что ответ у вас тоже другой.
avatar
wrmngr, Вы правы по существу и были самым настойчивым из тех, кто предлагал оценить блуждание только внутри страницы. Я когда-то поближе знакомился со случайным блужданием и знал ответ. Но был еще и фактор «блондинки» из анекдота, про который автор упоминал. Чтоб оценить, относится ли «блондинка» к 1/4 или к «равновероятно — упадет или останется на странице навсегда», как с динозаврами, надо было оценить сложность оценки «останется блуждать». При том, что оценка не очень сложна, она, imho, несколько выходит за рамки «наивного теорвера», да и автор вроде брал ответственность на себя (он же ничем не рисковал, зная ответ). Поэтому мне пришлось ограничиться намеком.

Обратили внимание, что тема случайного блуждания с «математическими» алгоритмами извлечения из него прибыли, да и вообще любая тема с «математикой» пользуется успехом на SL? Месяц-два назад была пара таких постов с очевидными ошибками и оценку они получили высокую.
Гусев Владимир Павлович со свойственной ему искренностью сказал бы:«Какое случайное блуждание, какой теорвер, здесь не казино и мы не в карты или рулетку играем и не монетку бросаем».
Я человек деликатный и прямо так сказать не могу, но попробовать зародить сомнение я обязан.
Борис Гудылин, тут вот какая штука...
Сам теорвер конечно не обеспечивает преимущества на рынке, но позволяет (разумеется, после некоторого осмысления базовых концепций) более адекватно оценивать выдвигаемые гипотезы о его свойствах.

К примеру, тоже самое монте-карло  при корректной методологии позволяет выявить эффект оверкурвфиттинга модели путём разрушения автокорреляционных связей исходного временного ряда. Конечно, тут тоже нужно чётко понимать границы применимости.

Господин Гусев намеренно или неосознанно подобрал в том видео несколько низколиквидных сильнотрендовых активов и делает скоропалительные и ложные, на мой взгляд, выводы.

Если взять, например, кросс EURUSD, то после нормировки на локальную волатильность распределение приращений становится почти идеально Гауссовым без значимых автокорреляций. Это тот самый сильноэффективный рынок из учебников. И заработать на нем чертовски сложно. Но чтобы это осознать, приходится порой применять и матстат и теорвер.

avatar
wrmngr, я понял Вас. Нет у нас точек соприкосновения, учет локальной волатильности не в счет. Мы по-разному видим рынок, моего в учебниках нет. И математика у нас тоже разная. Что же, «пусть расцветают сто цветов, пусть соревнуются сто учений».
Борис Гудылин, ваш подход безусловно интересен. Насколько я понял удалось выявить странные аттракторы для цены определенного вида, причем, что мне удивительно, на линейной шкале времени.

Для построений типа ренко-каги не пробовали подобное?

Еще интересно как это отрабатывает на самых ликвидных рынках? например фьючи на проц.ставку eurodollar, на десятилетние ноты, SnP500, nasdaq, нефть, золото, трежурис и бунды, спот eurusd и usdjpy
avatar
wrmngr, верно, несколько семейств странных аттракторов. Шкалы я пробовал разные, кванты по времени, по объемам, по цене — есть некоторые практические нюансы, самую удобную выберу в последний момент. Даже пару постов по чьим-то идеям из квантовой механики сделал.
Изредка отслеживаю поведение акций и фьючерсов в большом диапазоне, но глаз уже на автомате цепляется за известные мне формы и на других графиках. 
Вот мой сравнительно свежий комментарий, некоторые моменты относительно моего выбора. 
smart-lab.ru/blog/371377.php#comment6659874
Борис Гудылин, понял, благодарю за информацию
avatar
Все верно, теорвер как отрасль вообще нахер не нужен. Всегда проще сформулировать задачу программно, я уж не говорю о том, что тут мы имеем реальные результаты, а в математике — всего лишь досужие домыслы дядек, которые могут быть и не проверены.

Правда, я не понимаю, причем тут метод Монте Карло?  Разве под «монте-карло» понимается честный рандом, не математический? Программный рандом обычно честный, там используется температура проца и пр.
avatar

Монте-карло хорошая вещь. Но тут из пушки по воробьям, конечно. И так понятно, что финальные состояния «упасть сверху страницы», «упасть в сторону», «упасть снизу страницы», «перейти на 107» равновероятны. 

С другой стороны, сформулируем задачу «Какова вероятность упасть, ни разу не подойдя к границе страницы 107?» (без разницы, пересечь, или просто подойти к границе), и получаем задачу чуть сложнее, для решения которой придется подумать, а вот монте-карло решит запросто)

avatar
Lafert, только чтобы применять Монте-Карло, нужно задачу уже наполовину решить — задать правильные условия и соотношения.
А по сформулированной задаче, которая от исходной отличается только тем, что «107» на клетку ближе, чем остальные границы, можно оценить вероятность упасть как 10/21.
avatar
А если книга будет большая размером 100 на 100 см, то ответ такой же будет 0,25?
avatar
Antonovka, да, для любой квадратной страницы конечных размеров
avatar

теги блога _sk_

....все тэги



UPDONW
Новый дизайн