Вероятности и неприятности. Математика повседневной жизни
- Автор: Сергей Самойленко
- Жанр: Научно-популярная литература
- Дата выхода: 2022
- Цикл: Наука для всех
Читать книгу "Вероятности и неприятности. Математика повседневной жизни"
«Лила» и игра с бесконечностью
Характерную цикличность в случайном на первый взгляд процессе я наблюдал, принимая участие в игре «Лила» (рис. 6.14). Это разновидность игры «Лестницы и змеи», у которой, как говорят, древние индийские корни. Участники перемещают свои фишки (амулеты) согласно выпадающим числам на кубике, следуя переходам — «лестницам» или «стрелам», ведущим вперед, и «змеям», возвращающим игрока назад. Основной смысл заключается в философских и эзотерических толкованиях траектории, которую проходит игрок. В нашей компании были опытные люди, они делились впечатлениями от прошлых игр и восхищались «явно неслучайными» совпадениями траекторий игры и реальной жизни, точному их повторению от партии к партии — как у одного и того же, так и у разных участников.
Рис. 6.14. Доска для игры «Лила»
В игре 72 состояния, и правила бросания кубика нетривиальны: они делают более вероятными близкие переходы, но допускают и далекие скачки; кроме того, «лестницы» и «змеи» добавляют путаницы. Действительно, в игре много элементов случайности, но она все равно остается марковской, поскольку ближайшее будущее игрока определяется только текущим его состоянием. А значит, сам процесс можно анализировать на предмет наличия в нем повторяющихся последовательностей или наиболее вероятных состояний.
Несложно написать программу, которая могла бы играть в «Лилу», не задумываясь о сокровенном смысле состояний и переходов, и которую можно было бы использовать в анализе методом Монте-Карло. Приведу для тех, кому, как и мне, любопытно поэкспериментировать, алгоритм для одного шага.
Переходы по лестницам и змеям могут быть описаны ассоциативным массивом
Jumps = { 10:23, 16:4, 61:3, 20:32, 22:60, 24:7, 27:41, 28:50, 29:6, 37:66, 45:67, 46:62, 52:35, 54:68, 55:2, 61:3, 63:13, 72:51, 68:1 }
Вход: текущее состояние (номер клетки) s
если (jumps содержит состояние s), вернуть jumps[s]
m:= случайное целое число от 1 до 6
если (m = 6), m:= m + случайное число от 1 до 6
если (s > 60), m:= min(m,72-s)
вернуть s + m
Вот что можно сказать после сотни тысяч партий. Средняя продолжительность игры (то есть достижения 68-й клетки) составляет 41,5 шага, при этом в половине партий игра закончится после 31 шагов. Это довольно много: учитывая, что шаги совершаются по очереди четырьмя-пятью участниками, игра может длиться несколько дней. Клетки посещаются неравновероятно, и разброс вероятностей достаточно велик.
Но любому математику интереснее не получить ответ из эксперимента, а вывести из свойств исследуемой системы. Мы рассмотрим
Рис. 6.15. Графическое представление матрицы переходов для «Лилы». Ненулевые элементы показаны кружками, размеры отражают их величину
Эта квадратная матрица имеет столько строк, сколько существует состояний (клеток) игры. Насыщенность цвета каждой клеточки показывает вероятность перехода с позиции, указанной по вертикали, на позицию по горизонтали. Стрелки приводят пример, соответствующий вероятности перехода с 40-й клетки на 50-ю. Широкая полоса вокруг диагонали соответствует переходам с помощью кубика, прочие отмеченные точки — прыжкам, диктуемым «стрелами» и «змеями». Игра имеет одно
Точные параметры можно получить не прибегая к методу Монте-Карло, а используя только матрицу переходов. Квадратные матрицы образуют
Рис. 6.16. Матрицы переходов, возведенные в степени 2, 4, 10 и ∞
Необычно видеть что-то конечное и нетривиальное, возведенное в бесконечную степень. Привычные для нас вещественные числа (положительные) при возведении в большие степени либо увеличиваются до бесконечности, либо стремятся к нулю, и только числа 0 и 1 не изменяются.
Матрицы существенно раздвигают горизонты математического сознания, порождая необычные, порой причудливые, но полезные алгебраические системы[26]. Матрица переходов относится к классу
Такие матрицы называют
Предельная матрица получилась «полосатой»: все ее столбцы одинаковы, и полоски говорят нам, что вероятность перехода определяется только конечной клеткой и не зависит от начала пути: прошлое в марковском процессе теряется безвозвратно (как форма тела в его тени). Любая строка этой предельной матрицы дает точное распределение «популярности» клеток. Полученный набор вероятностей для состояний игры образует особый вектор π, который называется
Рис. 6.17. Стационарное состояние игры отражает распределение вероятности посещения клеток. Точками показаны точные значения вероятностей, а столбиками — полученные после ста тысяч шагов игры
Если бы мы оставили состояние 68 поглощающим, как предписывают правила игры, в бесконечном будущем можно было бы ожидать, что все партии сойдутся к нему. Инвариантом в этом случае был бы вектор, в котором от нуля отлична лишь 68-я позиция. Но и такая матрица перехода может быть полезна. Она дает нам возможность проанализировать время окончания игры. Матрица
Рис. 6.18. Распределение длительности партии в игру «Лила», полученное в ходе ста тысяч экспериментов и теоретически
Так можно не играя вычислить, что изменится при каких-либо поправках к правилам: например, смене поглощающего состояния, добавлении или удалении переходов, усложнении выбрасывания кубика и т. п. Матричные вычисления, в том числе точные, можно выполнять очень быстро, почти мгновенно, в отличие от имитационного моделирования, так что допустимо поручить машине оптимизацию правил игры с целью сделать ее интереснее, создавать маловероятные «ценные клетки» и контролировать при этом длительность партии.
Кстати, в вычислениях для этой главы я использовал один красивый прием, имеющий отношение к нашей второй сквозной теме: алгебраическим структурам. С давних пор известен способ умножения целых чисел, который зовется то египетским, то способом русского крестьянина и представляет интерес не только своим практическим смыслом, но и глубокой математической основой и следующей из нее универсальностью. Вы без труда найдете его описание во многих книгах по популярной математике. Метод основан на двух очень простых равенствах, вполне очевидных даже для школьника:
Первое равенство позволяет уменьшить множитель
Но вот что делает этот метод по-настоящему замечательным: число