Продолжать или соскакивать?
Есть много задач на оптимальную остановку. Порой решения у них довольно лукавые...
Привет, друзья! Здесь, на этом канале, я публикую научно-популярные заметки в разных рубриках. Это первая из рубрики "Вероятность и теория игр". Будут еще и другие. Некоторые заметки, как эта, перенесены из моего Дзен-канала, но будут и новые. Эта пока публичная, но первая же уникальная будет уже закрытой.
Обычно в математике есть правильное решение, и всё на том. Но вот пример "луковицы", в которой несколько слоев истины.
Предположим, что человек играет в такую игру: с равными шансами его капитал либо увеличивается на 10%, либо уменьшается на 10%. И так много-много раз. Каково среднее значение капитала за данное число шагов, например, за тысячу?
Наивное рассуждение таково. «Что такое равные шансы?» — спросит человек, немного знакомый с теорией вероятностей. Это на большом интервале доля исходов приблизительно равная. Стало быть, примерно пополам разделятся выигрыши и проигрыши. Так? А ведь выиграть и потом проиграть по 10% — это проиграть (1%). И в другом порядке — тоже (кстати, это само по себе может быть сюрпризом — проигрывать-то проще, чем выигрывать. В самом деле, (1-a)(1+a)<1, причем от порядка сомножителей результат, разумеется, не зависит.
Выходит, что за тысячу партий будет примерно по 500 пар «выиграл-проиграл», и на каждой теряем один процент — в общем, ничего радостного. Проиграет этот игрок все деньги.
Точное решение, однако, другое. За одну партию человек в среднем при своих — выигрыш и проигрыш равны по величине и шансы у них равные. Сыграв N партий, он имеет некоторое среднее X — а еще одна партия его не меняет. Далее по индукции получаем, что средний капитал равен начальному, то есть средний выигрыш — нуль.
Я специально не пишу детально — кто хочет, восстановит доказательство и получит удовольствие, а кто не хочет — на слово поверит.
Это решение точное, но правильным его не назовешь, и вот почему. Не поленитесь, напишите симулятор на вашем любимом языке программирования или в любимой электронной таблице. Увидите, как виртуальный игрок раз за разом спускает все деньги.
Давайте же выясним, в чем дело. А дело в траекториях. Тысяча партий порождает последовательность из нулей и единиц — траекторию. Все траектории имеют одну и ту же (очень маленькую) вероятность и приносят какой-то выигрыш, положительный или отрицательный. Вклад — это произведение выигрыша на вероятность. Среднее — сумма всех вкладов.
Так вот: некоторые траектории приносят очень много. Например, если все до единой партии выиграны. Или все, кроме одной — таких траекторий целая тысяча. Или две проиграны. Вклад таких траекторий значителен, хотя их суммарная вероятность невелика. А симметричные им траектории — например, если все партии проиграны — не компенсируют большой вклад своих напарниц. Если ты разорен на сотом, скажем, ходу — какая тебе разница, что будет дальше? Все траектории, в которых капитал упал в сто, скажем, раз и больше не поднялся, дают почти нулевой вклад.
На рисунке несколько траекторий, полученных на симуляторе в среде R. Голубая достигла ста: везучий игрок! Но тоже проиграл в итоге.
Итак, сравнительно большое среднее обусловлено вкладом очень редких, практически невозможных исходов. Правильным оказывается наивное рассуждение! Почти наверняка игрок разорится — хотя теоретически он должен в среднем остаться при своих.
Такой принцип часто встречается, но редко имеет такую четкую и практичную форму. Буду рад, если Вы подпишетесь на канал. До связи!