Необычно видеть что-то конечное и нетривиальное, возведенное в бесконечную степень. Привычные для нас вещественные числа (положительные) при возведении в большие степени либо увеличиваются до бесконечности, либо стремятся к нулю, и только числа 0 и 1 не изменяются.
Матрицы существенно раздвигают горизонты математического сознания, порождая необычные, порой причудливые, но полезные алгебраические системы[26]
. Матрица переходов относится к классуТакие матрицы называют
Предельная матрица получилась «полосатой»: все ее столбцы одинаковы, и полоски говорят нам, что вероятность перехода определяется только конечной клеткой и не зависит от начала пути: прошлое в марковском процессе теряется безвозвратно (как форма тела в его тени). Любая строка этой предельной матрицы дает точное распределение «популярности» клеток. Полученный набор вероятностей для состояний игры образует особый вектор π, который называется
Рис. 6.17.
Стационарное состояние игры отражает распределение вероятности посещения клеток. Точками показаны точные значения вероятностей, а столбиками — полученные после ста тысяч шагов игрыЕсли бы мы оставили состояние 68 поглощающим, как предписывают правила игры, в бесконечном будущем можно было бы ожидать, что все партии сойдутся к нему. Инвариантом в этом случае был бы вектор, в котором от нуля отлична лишь 68-я позиция. Но и такая матрица перехода может быть полезна. Она дает нам возможность проанализировать время окончания игры. Матрица
Рис. 6.18.
Распределение длительности партии в игру «Лила», полученное в ходе ста тысяч экспериментов и теоретическиТак можно не играя вычислить, что изменится при каких-либо поправках к правилам: например, смене поглощающего состояния, добавлении или удалении переходов, усложнении выбрасывания кубика и т. п. Матричные вычисления, в том числе точные, можно выполнять очень быстро, почти мгновенно, в отличие от имитационного моделирования, так что допустимо поручить машине оптимизацию правил игры с целью сделать ее интереснее, создавать маловероятные «ценные клетки» и контролировать при этом длительность партии.
Кстати, в вычислениях для этой главы я использовал один красивый прием, имеющий отношение к нашей второй сквозной теме: алгебраическим структурам. С давних пор известен способ умножения целых чисел, который зовется то египетским, то способом русского крестьянина и представляет интерес не только своим практическим смыслом, но и глубокой математической основой и следующей из нее универсальностью. Вы без труда найдете его описание во многих книгах по популярной математике. Метод основан на двух очень простых равенствах, вполне очевидных даже для школьника: