Вероятности и неприятности. Математика повседневной жизни - Сергей Борисович Самойленко

в том или ином настроении. Распределение длительностей полос отклонится от геометрического, но при этом большая часть полос будет короткой и какой-либо выделенной периодичности мы не отметим (рис. 6.13).

Рис. 6.13. Гистограмма для длительностей периодов постоянного настроения в последовательности, сгенерированной асимметричной цепью Маркова. Ступенчатая линия показывает геометрическое распределение из предыдущего примера

Цепи Маркова — мощный инструмент анализа случайных процессов, в которых кроется некий алгоритм или сценарий. Они дают нам своеобразный взгляд на процессы, привычно относимые к циклическим. Например, известная максима «история человечества ходит по кругу» часто трактуется так: в истории существуют некие циклы или даже периодичности. Доводится слышать, например, о том, что начало века сулит потрясения и войны. Рискуя уйти не в свою тему, возьму на себя смелость предположить, что на самом деле имеет смысл говорить не о буквальных циклах, а о более или менее устойчивых сценариях — закономерных цепочках, которые можно описать цепью Маркова. Среди таких цепей есть класс циклических, которые в самом деле способны создавать повторяющиеся последовательности. Однако настоящей детерминистической периодичности в их поведении нет. Случайно возникая в разные исторические периоды и в разных контекстах, такие циклы похожи друг на друга и могут создать ощущение исторического «дежавю». Изучать и описывать их полезно, но ожидать строгого календарного плана, пожалуй, не стоит.

«Лила» и игра с бесконечностью

Характерную цикличность в случайном на первый взгляд процессе я наблюдал, принимая участие в игре «Лила» (рис. 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 шагов. Это довольно много: учитывая, что шаги совершаются по очереди четырьмя-пятью участниками, игра может длиться несколько дней. Клетки посещаются неравновероятно, и разброс вероятностей достаточно велик.

Но любому математику интереснее не получить ответ из эксперимента, а вывести из свойств исследуемой системы. Мы рассмотрим матрицу переходов M для игры, она показана на рис. 6.15.

Рис. 6.15. Графическое представление матрицы переходов для «Лилы». Ненулевые элементы показаны кружками, размеры отражают их величину

Эта квадратная матрица имеет столько строк, сколько существует состояний (клеток) игры. Насыщенность цвета каждой клеточки показывает вероятность перехода с позиции, указанной по вертикали, на позицию по горизонтали. Стрелки приводят пример, соответствующий вероятности перехода с 40-й клетки на 50-ю. Широкая полоса вокруг диагонали соответствует переходам с помощью кубика, прочие отмеченные точки — прыжкам, диктуемым «стрелами» и «змеями». Игра имеет одно поглощающее состояние: достигнув ячейки 68, игрок заканчивает партию. Но пока мы это правило заменим другим: пусть игрок, попав в клетку 68, вновь начинает с первой позиции. Этот переход показан незакрашенным кружком на матрице. Позже я объясню, для чего нам потребовалось таким способом закольцевать игру.

Точные параметры можно получить не прибегая к методу Монте-Карло, а используя только матрицу переходов. Квадратные матрицы образуют алгебру: их можно по определенным правилам складывать и вычитать, умножать на число, перемножать и «делить» (умножать на обратную матрицу). Как и для чисел, многократное умножение матрицы на себя можно рассматривать как возведение в целочисленную степень. В случае с матрицей переходов для цепи Маркова возведение в степень n дает нам распределение вероятностей для всех переходов из клетки в клетку через n шагов. Так мы получаем своего рода «машину времени», способную мгновенно переместить нас в будущее. Вот как выглядят матрицы переходов игры «Лила» после 2, 3, 10 и, как это ни странно звучит, бесконечного числа умножений (рис. 6.16).

Рис. 6.16. Матрицы переходов, возведенные в степени 2, 4, 10 и ∞

Необычно видеть что-то конечное и нетривиальное, возведенное в бесконечную степень. Привычные для нас вещественные числа (положительные) при возведении в большие степени либо увеличиваются до бесконечности, либо стремятся к нулю, и только числа 0 и 1 не изменяются.

Матрицы существенно раздвигают горизонты математического сознания, порождая необычные, порой причудливые, но полезные алгебраические системы[26]. Матрица переходов относится к классу стохастических, их характеризует то,