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

что сумма элементов любой их строки равна единице. Это связано с тем, что каждая строка соответствует какому-то состоянию системы, а ее элементы — вероятностям перехода из этого состояния в другие. Рассматриваются все возможные варианты переходов, поэтому сумма всех вероятностей равна единице. Возведение стохастической матрицы в целочисленную степень оставляет ее стохастической. В пределе же мы получили матрицу, которая не изменяется при умножении на саму себя:

M∞∙M∞ = M∞.

Такие матрицы называют идемпотентными. Может показаться, что это какой-то экзотический случай, но идемпотентны все преобразования проекции, а значит, и представляющие их матрицы. Вообразите преобразование, для каждого трехмерного объекта возвращающее его тень на некой фиксированной стене. В процессе часть информации о форме объекта неизбежно теряется, а другая остается неизменной. На этом основаны занимательные задачи, в которых нужно определить, тело какой формы может отбросить указанные тени. А что случится с тенью, если мы еще раз спроецируем ее на эту же стену? Ровным счетом ничего, она не изменится. Можно точно показать, что любое преобразование проекции идемпотентно, но пример с тенью уже позволяет понять, что это означает и что это свойство не такая уж редкость. Многократное перемножение матрицы перехода для нашей марковской цепи привело нас к такому случаю. Эта предельная матрица отражает все мыслимые партии сразу. Впечатляет, но игра, определяемая такой матрицей, становится уже неинтересной.

Предельная матрица получилась «полосатой»: все ее столбцы одинаковы, и полоски говорят нам, что вероятность перехода определяется только конечной клеткой и не зависит от начала пути: прошлое в марковском процессе теряется безвозвратно (как форма тела в его тени). Любая строка этой предельной матрицы дает точное распределение «популярности» клеток. Полученный набор вероятностей для состояний игры образует особый вектор π, который называется стационарным состоянием цепи (рис. 6.17). Это и есть своеобразная «тень» игры, которая не меняется под действием матрицы перехода[27]: M∙π = π. Величины, обратные найденным нами вероятностям, характеризуют ожидаемое время достижения для каждой клетки. Например, для клетки 68, конечной в игре, инвариантный вектор дает вероятность достижения 2,4 %. Обратная величина равна 41,5, что совпадает со средней продолжительностью игры, полученной в эксперименте.

Рис. 6.17. Стационарное состояние игры отражает распределение вероятности посещения клеток. Точками показаны точные значения вероятностей, а столбиками — полученные после ста тысяч шагов игры

Если бы мы оставили состояние 68 поглощающим, как предписывают правила игры, в бесконечном будущем можно было бы ожидать, что все партии сойдутся к нему. Инвариантом в этом случае был бы вектор, в котором от нуля отлична лишь 68-я позиция. Но и такая матрица перехода может быть полезна. Она дает нам возможность проанализировать время окончания игры. Матрица Mn соответствует n шагам в игре, а значит, элемент (Mn)ij покажет вероятность достижения состояния j из состояния i за n шагов. Таким образом, мы можем построить точное распределение времени окончания игры, нарисовав график зависимости p(n) = (Mn)1,68, как показано на рис. 6.18.

Рис. 6.18. Распределение длительности партии в игру «Лила», полученное в ходе ста тысяч экспериментов и теоретически

Так можно не играя вычислить, что изменится при каких-либо поправках к правилам: например, смене поглощающего состояния, добавлении или удалении переходов, усложнении выбрасывания кубика и т. п. Матричные вычисления, в том числе точные, можно выполнять очень быстро, почти мгновенно, в отличие от имитационного моделирования, так что допустимо поручить машине оптимизацию правил игры с целью сделать ее интереснее, создавать маловероятные «ценные клетки» и контролировать при этом длительность партии.

Кстати, в вычислениях для этой главы я использовал один красивый прием, имеющий отношение к нашей второй сквозной теме: алгебраическим структурам. С давних пор известен способ умножения целых чисел, который зовется то египетским, то способом русского крестьянина и представляет интерес не только своим практическим смыслом, но и глубокой математической основой и следующей из нее универсальностью. Вы без труда найдете его описание во многих книгах по популярной математике. Метод основан на двух очень простых равенствах, вполне очевидных даже для школьника:

(2n)a = 2(na) = na + na,

(n + 1)a = na + a.

Первое равенство позволяет уменьшить множитель n за счет удвоения произведения, а второе — перейти к первому, если уменьшаемый множитель нечетный. Сами по себе эти равенства обладают свойствами ассоциативности и дистрибутивности[28] умножения, то есть носят фундаментальный характер, но поскольку единица — нейтральный элемент для умножения, они образуют весьма эффективную рекурсивную схему вычисления произведения. Эффективность связана с тем, что умножение — или многократное сложение — заменяется операцией удвоения, которая увеличивает результат существенно быстрее. Например, при перемножении чисел в пределах миллиона потребуется не более 20 шагов этого алгоритма.

Но вот что делает этот метод по-настоящему замечательным: число a можно заменить любым другим объектом, для которого определена ассоциативная операция сложения с нейтральным элементом. Такие объекты образуют структуру, называемую полугруппой с единицей, или моноидом. Дело в том, что умножение элемента моноида на целое число эквивалентно многократному сложению этого объекта с самим собой. А это значит, что, имея любой моноид, мы можем применить к нему метод русского крестьянина! Числа образуют моноид не только с операцией сложения, но и с операцией умножения, и тогда метод можно использовать для быстрого возведения в степень. Моноид с операцией умножения формируют и матрицы, а также представляемые ими линейные преобразования. Это позволяет очень быстро вычислить результат возведения матрицы в очень большую степень без потери точности. Чем я и воспользовался.

В завершение разговора об игре «Лила» перейдем к часто повторяющимся мотивам. Их тоже можно изучать не играя, а анализируя матрицу переходов. Вероятности для любой цепочки вычисляются как произведения вероятностей переходов, умноженных на вероятность попадания в начальную позицию:

P(3→5→13→15) = π3M3,5M5,13M13,15.

Так можно перебрать все цепочки длины 3, 4, 5 и т. д. и найти наиболее вероятные. Но такой поиск занял бы слишком много времени. Возможно отыскивать такие цепочки более целенаправленно. Для любой начальной клетки можно, пользуясь матрицей переходов, создать дерево возможных шагов, оставляя по мере построения несколько