Продолжаем исследовать законы подлости вместе с теорией вероятностей и прочей другой математикой. В этой серии статей я привожу выдержки из своей книжки Вероятности и неприятности.
Говорят, жизнь похожа на зебру: то белая полоса, то черная… А еще бывает, что к одной неприятности добавляется другая: и так все непросто в жизни, а тут еще кошка рожать принялась! То густо, то пусто! Одно к одному! Но самое печальное, что когда становится хорошо и в жизни наступает светлая полоса, то мысли закрадываются нехорошие: ох, не сглазить бы… ох, не придется ли за счастье расплачиваться… Знакомое ощущение? Об этом говорит один из законов мерфологии — второй закон Чизхолма:
Когда дела идут хорошо, что-то должно случиться в самом ближайшем будущем.
Но поскольку Френсис Чизхолм в своей оригинальной работе не дает детального анализа или доказательства этого закона, мы постараемся сами выяснить, кроется ли за этим какая-либо закономерность или нам так только кажется. А если это причуды математики, можно ли определить характерную длительность или частоту полосок на теле нашей зебры и от чего эти параметры зависят?
Характерную цикличность удач и неудач в случайном на первый взгляд процессе я наблюдал, принимая участие в игре «Лила». Это разновидность игры «Лестницы и змеи», у которой, как говорят, древние индийские корни. Участники перемещают свои фишки (амулеты) согласно выпадающим числам на кубике, следуя переходам — «лестницам» или «стрелам», ведущим вперед, и «змеям», возвращающим игрока назад. Основной смысл заключается в философских и эзотерических толкованиях траектории, которую проходит игрок. В нашей компании были опытные люди, они делились впечатлениями от прошлых игр и восхищались «явно неслучайными» совпадениями траекторий игры и реальной жизни, точному их повторению от партии к партии — как у одного и того же, так и у разных участников.
В игре 72 состояния, и правила бросания кубика нетривиальны: они делают более вероятными близкие переходы, но допускают и далекие скачки; кроме того, «лестницы» и «змеи» добавляют путаницы. Действительно, в игре много элементов случайности, но она все равно остается марковской, поскольку ближайшее будущее игрока определяется только текущим его состоянием. А значит, сам процесс можно анализировать на предмет наличия в нем повторяющихся последовательностей или наиболее вероятных состояний.
Несложно написать программу, которая могла бы играть в «Лилу», не задумываясь о сокровенном смысле состояний и переходов, и которую можно было бы использовать в анализе методом Монте-Карло.
Вот что можно сказать после сотни тысяч партий. Средняя продолжительность игры (то есть достижения 68-й клетки) составляет 41.5 шага, при этом в половине партий игра закончится после 31 шагов. Это довольно много: учитывая, что шаги совершаются по очереди четырьмя-пятью участниками, игра может длиться несколько дней. Клетки посещаются неравновероятно, и разброс вероятностей достаточно велик.
Но любому математику интереснее не получить ответ из эксперимента, а вывести из свойств исследуемой системы. Мы рассмотрим матрицу переходов M для игры, она показана на рисунке:
Точные параметры можно получить не прибегая к методу Монте-Карло, а используя только матрицу переходов. Квадратные матрицы образуют алгебру: их можно по определенным правилам складывать и вычитать, умножать на число, перемножать и «делить» (умножать на обратную матрицу). Как и для чисел, многократное умножение матрицы на себя можно рассматривать как возведение в целочисленную степень. В случае с матрицей переходов для цепи Маркова возведение в степень n дает нам распределение вероятностей для всех переходов из клетки в клетку через n шагов. Так мы получаем своего рода «машину времени», способную мгновенно переместить нас в будущее. Вот как выглядят матрицы переходов игры «Лила» после 2, 3, 10 и, как это ни странно звучит, бесконечного числа умножений.
Необычно видеть что-то конечное и нетривиальное, возведённое в бесконечную степень. Привычные для нас вещественные числа (положительные) при возведении в большие степени либо увеличиваются до бесконечности, либо стремятся к нулю, и только числа 0 и 1 не изменяются.
Мы уже неоднократно убеждались в том, что матрицы существенно раздвигают горизонты математического сознания, порождая необычные, порой причудливые, но полезные алгебраические системы. Матрица переходов относится к классу стохастических, их характеризует то, что сумма элементов любой их строки равна единице. Это связано с тем, что каждая строка соответствует какому-то состоянию системы, а ее элементы — вероятностям перехода из этого состояния в другие. Рассматриваются все возможные варианты переходов, поэтому сумма всех вероятностей равна единице. Возведение стохастической матрицы в целочисленную степень оставляет ее стохастической.В пределе же мы получили матрицу, которая не изменяется при умножении на саму себя:
Такие матрицы называют идемпотентными. Может показаться, что это какой-то экзотический случай, но идемпотентны все преобразования проекции, а значит, и представляющие их матрицы. Вообразите преобразование, для каждого трехмерного объекта возвращающее его тень на некой фиксированной стене. В процессе часть информации о форме объекта неизбежно теряется, а другая остается неизменной. На этом основаны занимательные задачи, в которых нужно определить, тело какой формы может отбросить указанные тени. А что случится с тенью, если мы еще раз спроецируем ее на эту же стену? Ровным счётом ничего, она не изменится. Можно точно показать, что любое преобразование проекции идемпотентно, но пример с тенью уже позволяет понять, что это означает и что это свойство не такая уж редкость. Многократное перемножение матрицы перехода для нашей марковской цепи привело нас к такому случаю. Эта предельная матрица отражает все мыслимые партии сразу. Впечатляет, но игра, определяемая такой матрицей, становится уже неинтересной.
Предельная матрица получилась «полосатой»: все ее столбцы одинаковы, и полоски говорят нам, что вероятность перехода определяется только конечной клеткой и не зависит от начала пути: прошлое в марковском процессе теряется безвозвратно (как форма тела в его тени). Любая строка этой предельной матрицы дает точное распределение «популярности» клеток. Полученный набор вероятностей для состояний игры образует особый вектор π, который называется стационарным состоянием цепи. Он показан на рисунке:
Это и есть своеобразная «тень» игры, которая не меняется под действием матрицы перехода: M∙π = π. Величины, обратные найденным нами вероятностям, характеризуют ожидаемое время достижения для каждой клетки. Например, для клетки 68, конечной в игре, инвариантный вектор дает вероятность достижения 2,4%. Обратная величина равна 41,5, что совпадает со средней продолжительностью игры, полученной в эксперименте.
Если бы мы оставили состояние 68 поглощающим, как предписывают правила игры, в бесконечном будущем можно было бы ожидать, что все партии сойдутся к нему. Инвариантом в этом случае был бы вектор, в котором от нуля отлична лишь 68-я позиция. Но и такая матрица перехода может быть полезна. Она дает нам возможность проанализировать время окончания игры. Матрица Mⁿ соответствует n шагам в игре, а значит, элемент (Mⁿ)ᵢ,ⱼ покажет вероятность достижения состояния j из состояния i за n шагов. Таким образом, мы можем построить точное распределение времени окончания игры, нарисовав график зависимости p(n) = (Mⁿ)₁,₆₈ как показано на рисунке
Кстати, в вычислениях для этой главы я использовал один красивый прием, имеющий отношение к нашей второй сквозной теме: алгебраическим структурам. С давних пор известен способ умножения целых чисел, который зовется то египетским, то способом русского крестьянина и представляет интерес не только своим практическим смыслом, но и глубокой математической основой и следующей из нее универсальностью. Вы без труда найдете его описание во многих книгах по популярной математике. Метод основан на двух очень простых равенствах, вполне очевидных даже для школьника:
Первое равенство позволяет уменьшить множитель n за счет удвоения произведения, а второе — перейти к первому, если уменьшаемый множитель нечетный. Сами по себе эти равенства обладают свойствами ассоциативности и дистрибутивности умножения, то есть носят фундаментальный характер, но поскольку единица — нейтральный элемент для умножения, они образуют весьма эффективную рекурсивную схему вычисления произведения. Эффективность связана с тем, что умножение — или многократное сложение — заменяется операцией удвоения, которая увеличивает результат существенно быстрее. Например, при перемножении чисел в пределах миллиона потребуется не более 20 шагов этого алгоритма.
Но вот что делает этот метод по-настоящему замечательным: число a можно заменить любым другим объектом, для которого определена ассоциативная операция сложения с нейтральным элементом. Такие объекты образуют структуру, называемую полугруппой с единицей, или моноидом. Дело в том, что умножение элемента моноида на целое число эквивалентно многократному сложению этого объекта с самим собой. А это значит, что, имея любой моноид, мы можем применить к нему метод русского крестьянина! Числа образуют моноид не только с операцией сложения, но и с операцией умножения, и тогда метод можно использовать для быстрого возведения в степень. Моноид с операцией умножения формируют и матрицы, а также представляемые ими линейные преобразования. Это позволяет очень быстро вычислить результат возведения матрицы в очень большую степень без потери точности. Чем я и воспользовался.
В завершение разговора об игре «Лила» перейдем к часто повторяющимся мотивам. Их тоже можно изучать не играя, а анализируя матрицу переходов. Вероятности для любой цепочки вычисляются как произведения вероятностей переходов, умноженных на вероятность попадания в начальную позицию:
Так можно перебрать все цепочки длины 3, 4, 5 и т. д. и найти наиболее вероятные. Но такой поиск занял бы слишком много времени. Возможно отыскивать такие цепочки более целенаправленно. Для любой начальной клетки можно, пользуясь матрицей переходов, создать дерево возможных шагов, оставляя по мере построения несколько наиболее вероятных ветвей. Такой процесс называется поиском оптимального пути в ширину с отсечением. Действуя таким способом, можно отыскать самые часто наблюдаемые цепочки и выяснить, как распределяются цепочки по вероятности их наблюдения:
Должно быть, для всемогущего божества, способного видеть сколь угодно далекое будущее, играющего во все игры сразу, мир предстает достаточно скучной вырожденной идемпотентной матрицей. Впрочем, оставим наше мифическое божество разбираться с этой проблемой самостоятельно. Я привел этот пример здесь потому, что мне хотелось показать, как математика позволяет проанализировать структуру довольно сложной и стохастической игры. Предпринимались попытки анализа известной игры «Монополия», но здесь становится существенной роль эксперимента, поскольку процесс накопления игроками денег добавляет в процесс память — и он перестает быть марковским.
Несмотря на простоту и некоторую ограниченность, трудно переоценить важность концепции цепей Маркова. Если взяться перечислять области, в которых они используются, получится внушительный перечень не на одну страницу. В нем окажутся и симуляции реальности более сложной, чем игры; генерация текстов, музыки, речи, тестовых заданий для систем автоматического управления; поиск страниц в сети интернет; физика, химия, биология, генетика, экономика, социология, безопасность дорожного движения… даже в спорте используются цепи Маркова! Сама идея цепи появилась при работе Андрея Андреевича Маркова над темой, как кажется, весьма далекой от математики: анализом сочетаний гласных и согласных звуков в тексте романа А. С. Пушкина «Евгений Онегин».
Цепи Маркова — мощный инструмент анализа случайных процессов, в которых кроется некий алгоритм или сценарий. Они дают нам своеобразный взгляд на процессы, привычно относимые к циклическим. Например, известная максима «история человечества ходит по кругу» часто трактуется так: в истории существуют некие циклы или даже периодичности. Доводится слышать, например, о том, что начало века сулит потрясения и войны. Рискуя уйти не в свою тему, возьму на себя смелость предположить, что на самом деле имеет смысл говорить не о буквальных циклах, а о более или менее устойчивых сценариях — закономерных цепочках, которые можно описать цепью Маркова. Среди таких цепей есть класс циклических, которые в самом деле способны создавать повторяющиеся последовательности. Однако настоящей детерминистической периодичности в их поведении нет. Случайно возникая в разные исторические периоды и в разных контекстах, такие циклы похожи друг на друга и могут создать ощущение исторического «дежавю». Изучать и описывать их полезно, но ожидать строгого календарного плана, пожалуй, не стоит.