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

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

(n + 1)a = na + a.

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

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

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

P(3→5→13→15) = π₃M_3,5M_5,13M_13,15.

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

Вероятность для цепочки	Число цепочек
> 25%	3
> 10%	10
> 5%	64

Рис. 6.19. Наиболее часто наблюдаемые цепочки в игре «Лила»

Пример с игрой «Лила» напрямую не касается вопроса о полосах в реальной жизни, но заставляет задуматься. Должно быть, для всемогущего божества, способного видеть сколь угодно далекое будущее, играющего во все игры сразу, мир предстает достаточно скучной вырожденной идемпотентной матрицей. Впрочем, оставим наше мифическое божество разбираться с этой проблемой самостоятельно. Я привел этот пример здесь потому, что мне хотелось показать, как математика позволяет проанализировать структуру довольно сложной и стохастической игры. Предпринимались попытки анализа известной игры «Монополия», но здесь становится существенной роль эксперимента, поскольку процесс накопления игроками денег добавляет в процесс память — и он перестает быть марковским.

Несмотря на простоту и некоторую ограниченность, трудно переоценить важность концепции цепей Маркова. Если взяться перечислять области, в которых они используются, получится внушительный перечень не на одну страницу. В нем окажутся и симуляции реальности более сложной, чем игры; генерация текстов, музыки, речи, тестовых заданий для систем автоматического управления; поиск страниц в сети интернет; физика, химия, биология, генетика, экономика, социология, безопасность дорожного движения… даже в спорте используются цепи Маркова![29]

Почему автобуса все нет?!

Говоря о пуассоновском процессе, мы различали частоту и интенсивность потока событий. Это важно понимать, слушая новости или читая результаты научных исследований. Например, на сегодняшний день сейсмологи, увы, не могут предсказать конкретное землетрясение: его время, место и силу. Зато наработаны методики долгосрочного сейсмического прогноза для какого-то региона, но их результаты формулируются на языке теории вероятностей. Что с ними делать — не всегда очевидно.