Но вот что делает этот метод по-настоящему замечательным: число a можно заменить любым другим объектом, для которого определена ассоциативная операция сложения с нейтральным элементом. Такие объекты образуют структуру, называемую полугруппой с единицей, или моноидом. Дело в том, что умножение элемента моноида на целое число эквивалентно многократному сложению этого объекта с самим собой. А это значит, что, имея любой моноид, мы можем применить к нему метод русского крестьянина! Числа образуют моноид не только с операцией сложения, но и с операцией умножения, и тогда метод можно использовать для быстрого возведения в степень. Моноид с операцией умножения формируют и матрицы, а также представляемые ими линейные преобразования. Это позволяет очень быстро вычислить результат возведения матрицы в очень большую степень без потери точности. Чем я и воспользовался.
В завершение разговора об игре «Лила» перейдем к часто повторяющимся мотивам. Их тоже можно изучать не играя, а анализируя матрицу переходов. Вероятности для любой цепочки вычисляются как произведения вероятностей переходов, умноженных на вероятность попадания в начальную позицию:
P(3→5→13→15) = π3M3,5M5,13M13,15.
Так можно перебрать все цепочки длины 3, 4, 5 и т. д. и найти наиболее вероятные. Но такой поиск занял бы слишком много времени. Возможно отыскивать такие цепочки более целенаправленно. Для любой начальной клетки можно, пользуясь матрицей переходов, создать дерево возможных шагов, оставляя по мере построения несколько наиболее вероятных ветвей. Такой процесс называется поиском оптимального пути в ширину с отсечением. Действуя таким способом, можно отыскать самые часто наблюдаемые цепочки и выяснить, как распределяются цепочки по вероятности их наблюдения (рис. 6.19).
Вероятность для цепочки Число цепочек > 25% 3 > 10% 10 > 5% 64
Рис. 6.19. Наиболее часто наблюдаемые цепочки в игре «Лила»
Пример с игрой «Лила» напрямую не касается вопроса о полосах в реальной жизни, но заставляет задуматься. Должно быть, для всемогущего божества, способного видеть сколь угодно далекое будущее, играющего во все игры сразу, мир предстает достаточно скучной вырожденной идемпотентной матрицей. Впрочем, оставим наше мифическое божество разбираться с этой проблемой самостоятельно. Я привел этот пример здесь потому, что мне хотелось показать, как математика позволяет проанализировать структуру довольно сложной и стохастической игры. Предпринимались попытки анализа известной игры «Монополия», но здесь становится существенной роль эксперимента, поскольку процесс накопления игроками денег добавляет в процесс память — и он перестает быть марковским.
Несмотря на простоту и некоторую ограниченность, трудно переоценить важность концепции цепей Маркова. Если взяться перечислять области, в которых они используются, получится внушительный перечень не на одну страницу. В нем окажутся и симуляции реальности более сложной, чем игры; генерация текстов, музыки, речи, тестовых заданий для систем автоматического управления; поиск страниц в сети интернет; физика, химия, биология, генетика, экономика, социология, безопасность дорожного движения… даже в спорте используются цепи Маркова![29]
Почему автобуса все нет?!
Говоря о пуассоновском процессе, мы различали частоту и интенсивность потока событий. Это важно понимать, слушая новости или читая результаты научных исследований. Например, на сегодняшний день сейсмологи, увы, не могут предсказать конкретное землетрясение: его время, место и силу. Зато наработаны методики долгосрочного сейсмического прогноза для какого-то региона, но их результаты формулируются на языке теории вероятностей. Что с ними делать — не всегда очевидно.
Например, для Авачинского залива, на берегах которого расположен Петропавловск-Камчатский, в 2018 году был дан такой прогноз: «Суммарная вероятность землетрясений с магнитудой более 7,7, которые могут иметь силу 7–9 баллов в г. Петропавловске-Камчатском, может достигать на следующее пятилетие 52,3 %». Что это значит? Завтра тряхнет? А когда? А где? Увы, на такие прямые вопросы мы ответить пока не в силах. Интерпретируя это сообщение, не стоит мыслить о вероятности как о мере частоты событий. Конечно, если повторить пятилетний период сто раз, то можно заключить, что в ближайшие 500 лет произойдет примерно 52 землетрясения. Но этот вывод будет верным только при условии неизменности потока, а уже через месяц прогноз изменится. Интенсивность похожа в этом смысле на мгновенную скорость движения: чтобы измерить, что вы двигаетесь со скоростью 60 км/ч, не обязательно ехать целый час именно с таким показателем на спидометре. И, главное, данный учеными прогноз не говорит о том, что между землетрясениями проходит десять лет, как можно предположить, разделив 500 лет на 52 события. Таким образом, если на протяжении десяти лет не было сильного землетрясения, это не значит, что оно произойдет не сегодня-завтра. Оно будет, конечно. Но сколько именно придется ждать — неизвестно.
Посмотрите, как меняется уровень сейсмической активности Камчатского региона для разных масштабов времени (рис. 6.20, изображение взято с сайта Монитора сейсмической активности Камчатского филиала Единой геофизической службы РАН).
Рис. 6.20. На смену пониженному уровню активности приходит повышенный, активность «дышит», но не периодично, а подобно все тому же случайному блужданию с релаксацией
Но землетрясения — всё же неприятные явления, и пусть бы их не случалось подольше. Бывают события, которых ждешь с большим нетерпением, например прибытие автобуса. Приходя на остановку, мы, конечно, желаем мгновенно сесть на нужный маршрут, но чаще всего это не удается. Тогда, если в этом месте действует четкое расписание, мы смотрим на него, потом на часы, а затем погружаемся в книжку или телефон. Но где-нибудь в середине маршрута часто вместо расписания указывается интервал движения транспорта, например 15 минут. Это значит, что мы уже далеко от станции, с которой автобусы выходят точно по расписанию, и накапливается некоторая ошибка, делающая прибытие транспорта случайным. И вот тут надо иметь в виду, что в среднем придется ждать именно четверть часа, независимо от того, когда вы приходите на остановку. Вот если бы автобусы приходили с периодичностью 15 минут, среднее время ожидания составило бы половину периода — 7,5 минуты. Но с интенсивностью так не выйдет! При отсутствии дополнительных условий движение транспорта моделируют пуассоновским потоком, а это значит, что время ожидания автобуса будет подчиняться экспоненциальному закону с той же интенсивностью. Но математическое ожидание для экспоненциально распределенной величины с интенсивностью λ равно 1/λ, откуда и следует наш вывод. И что совсем обидно — количество времени, уже проведенного вами на остановке, никак не влияет на вероятность того, что автобус вот-вот подойдет. Это свойство экспоненциального распределения — отсутствие памяти, связанное с независимостью пуассоновских событий.
Впрочем, если быть точным, то дела с ожиданием автобуса обстоят еще хуже. Измеряемый наблюдателем случайный отрезок времени между машинами статистически больше 1/λ, и вероятность длительного интервала выше, чем среднего. Такой парадокс мы уже встречали — это парадокс наблюдателя или инспектора.
* * *Подведем итог. Приходя на остановку, нужно четко принять решение: ждать или идти пешком. Размышлять на тему: подождать еще или уже пойти — только обрекать себя на встречу с законом подлости. Ведь если вы, прождав 17 минут, плюнете и пойдете пешком, вас, весьма вероятно, обгонит долгожданный автобус, а то и два.
Несправедливость, к которой приводит парадокс инспектора, демонстрирует кривая Лоренца (рис. 6.21). Интересно, что она в случае экспоненциального распределения одинакова для любых интенсивностей. Таким образом, для всех пуассоновских процессов верно утверждение: половина общего времени наблюдения приходится на 20 % случаев, когда это очередное событие задерживается. К этому выводу можно прийти, увидев, что на кривой Лоренца 50 % общего времени приходится на 80 % интервалов, в оставшиеся 20 % попали длинные интервалы, поглощающие половину времени ожидания. Коэффициент Джини для экспоненциального распределения равен в точности 1/2.
Рис. 6.21. Кривая Лоренца для экспоненциального распределения не зависит от его параметра (интенсивности)
Глава 7. Прелести чужой очереди
Я размышляю о законах подлости, стоя в аэропорту в очереди на регистрацию пассажиров и оформление багажа. Хвост длинный, люди разные и заметные со всеми своими сумками, детьми или клетками. Сзади слышу ворчание: «Как обычно, наша очередь тормозит. Вон, гляди, тот усатый в кепке наравне с нами стоял, а теперь вон где… Вот ведь закон подлости!» Этот закон зовется наблюдением Этторе:
Соседняя очередь всегда движется быстрее.Что же это — психологический эффект или причуды математики?
Еще раз про пуассоновский процесс
Мы уже достаточно знаем о случайных процессах, чтобы немного проанализировать очередь, в которой стоим. За неимением других данных, разумно предположить, что выход из нее происходит по-пуассоновски: пассажиры подходят к стойке регистрации и проводят там какое-то время, не зависящее от времени обработки данных других пассажиров. Перемещение наблюдателя, стоящего в очереди, будет иметь вид монотонно изменяющейся ступенчатой линии, с одинаковыми шагами через случайные промежутки времени, подчиненные экспоненциальному распределению. Пара реализаций примеров пуассоновских процессов с одинаковой интенсивностью приведена на рис. 7.1. Обычно пуассоновский процесс накапливает события, и его изображение выглядит как «лесенка», растущая со