Вероятности и неприятности. Математика повседневной жизни - [45]

M^∞∙M^∞ = M^∞.

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

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

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

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

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

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

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

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

(n + 1)a = na + a.

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

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