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

Стратегия балбеса

Для анализа суеты нам опять потребуются случайные процессы. Один из самых простых из них, требующих минимума дополнительных предположений, — пуассоновский поток. Напомню, что его можно реализовать, случайно распределяя известное количество независимых событий по ограниченному временному интервалу. Хорошими примерами могут быть удары капель дождя по крыше, поток частных автомобилей на дороге, сильные землетрясения и т. п.

Но что мы получим, если события перестанут быть независимыми и начнут образовывать упорядоченную цепочку? Скажем, пусть в цепочке событий {A,B,C} B может случиться только после A, но перед C. При этом моменты, в которые эти события произойдут, останутся случайными. Посмотрим, как смогут разместиться такие упорядоченные цепочки на ограниченном временном интервале.

Первое событие мы расположим в произвольной точке, второе — тоже случайно, но обязательно после первого, третье — после второго и т. д. Для каждого следующего этапа будет оставаться все меньше времени, так что к правой части интервала (перед дедлайном) должно наблюдаться заметное увеличение интенсивности процесса. Рано или поздно время для выполнения задач закончится, и цепочка завершится. Назовем построенный нами процесс стохастической цепочкой с дедлайном, а выбранную безалаберную стратегию выполнения работы — стратегией балбеса. На рисунке 8.1 показан пример построенной таким образом цепочки из пяти этапов работы, на которую было отпущено 20 дней.

Рис. 8.1. Пример стохастической цепочки с дедлайном. В данном случае пять дел выполнить удалось, можно успеть шестое, а на семь времени уже не хватит

Понятно, что, выполняя задачи в соответствии с мерфологической аксиомой Дехэя: «Простую работу можно отложить, потому что всегда будет время ее сделать потом», — непросто уложиться в сроки. Но можно ли как-то проанализировать это явление? Сформулируем задачу, взяв в качестве испытуемого, скажем, театрального режиссера. Пусть в распоряжении режиссера и его труппы имеется n дней для постановки некоего действа. Подготовка разбивается на k последовательных репетиционных этапов, каждый из которых требует день на выполнение. Какова вероятность не уложиться в срок, если действовать согласно описанному нами процессу выполнения работ? Подготовка мероприятия требует вовлечения разных людей и различных производственных процессов, возможны накладки, болезни или попросту хандра — все предпосылки к реализации нашей стохастической цепочки с дедлайном.

Для начала я обратился к имитационному моделированию, чтобы выяснить, как распределяется длина цепочек, которые удается выполнить в ограниченный промежуток времени заданной длины, пользуясь стратегией балбеса.

Вычисления состояли в генерации стохастических цепочек и подсчете их длин для различных ограничений по времени по следующему алгоритму.

Вход: число дней n

Повторять, пока не набрано нужное число цепочек

· · · · x:= n

· · · · k:= 0

· · · · Повторять, пока x>0

· · · · · · · · выбрать случайное целое число x ~ Uniform([0,x])

· · · · · · · · увеличить счетчик k

· · · · конец

· · · · добавить k в гистограмму

конец

Вот какая гистограмма получается, например, для n = 10 (рис. 8.2).

Рис. 8.2. Гистограмма функции вероятности для длины цепочек, которые удается выполнить в отведенный срок. Синей линией показано распределение Пуассона с интенсивностью, соответствующей наблюдаемой средней длине цепочек

Подсчитывая события в настоящем пуассоновском потоке с интенсивностью λ, мы придем к упоминавшемуся уже распределению Пуассона:

которое, напомню, описывает вероятность получить ровно k событий в единичном интервале времени. Распределение внешне похоже на пуассоновское, но оказалось, что это все же не оно. Разберемся, откуда взялись именно такие доли.

Отвлечемся от дел и сроков и формально опишем исследуемый процесс. Рассмотрим ряд из n пронумерованных ячеек. Процесс состоит в последовательном случайном размещении точек по ним. Первая может оказаться в любой ячейке с равной вероятностью; пусть это будет ячейка с номером i₁. Следующая точка может оказаться в любой ячейке с номером i₂ > i₁. Для всех последующих точек i_k > i_k–1. Процесс завершится, когда i_k = n. Нас интересует вероятность того, что для заданного n > k удастся разместить менее k точек.

Мы будем рассуждать, рассматривая размещение точек «с конца», в обратном порядке. Любая цепочка завершается размещением последней точки в последней ячейке. Шансов не разместить какую-то одну точку нет, поскольку по условиям для первой точки все ячейки свободны. Короткие цепочки из двух точек устроены так: в последней ячейке располагается вторая, последняя точка (с вероятностью 1/n), а на расположение первой точки ограничений нет, так что вероятность для k = 2 равна 1/n. Дальше можно действовать индуктивно. Для произвольного k последняя точка обязательно должна оказаться в последней ячейке; это может случиться с вероятностью 1/n. Потом мы можем поместить предпоследнюю точку в любую из свободных ячеек, скажем с номером m, сведя при этом задачу к случаю (k — 1) точек и (n — m) ячеек. Выбор m ограничен сверху числом (k — 2), поскольку две точки — последняя и предпоследняя — уже на местах. У нас уже есть способ получить точное решение искомой задачи, но для этого нужно знать решения всех входящих в нее подзадач:

Такое определение функции называется рекуррентным. Чтобы им можно было воспользоваться, необходимо знать решение некоторых базовых подзадач; в нашем случае это выражения для k = 0 и 1. Полученное рекуррентное соотношение позволяет вычислить точное распределение, но его трудно анализировать. Нужно привести его в конечную форму — формулу, содержащую фиксированное конечное число арифметических действий над хорошо известными функциями. Мне удалось получить такую форму, оказавшуюся весьма компактной:

Здесь символ S(n,k) обозначает так называемые числа Стирлинга первого рода. Они возникают в комбинаторике при подсчете циклических перестановок и в задачах о распределении рекордов[34]. По правде говоря, числа Стирлинга тоже вычисляются рекуррентным соотношением:

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

Эти величины выражаются через очень интересные гармонические числа:  или в конечной форме и  Эти числа играют важную роль в такой неожиданно сложной области математики, как теория чисел.

Казалось бы, что может быть проще, чем изучение чисел, тем более целых? Арифметику проходят в школе; со свойствами чисел, такими как делимость, мы знакомимся на личном опыте, пытаясь честно разделить пять рублей на троих. Но именно эта область математики ставит перед исследователем чрезвычайно сложные проблемы. Одна великая теорема Ферма чего стоит! От гармонических чисел дорожка ведет к дзета-функции Римана, а от нее — к великой загадке распределения простых чисел. Нам не потребуются результаты теории чисел явным образом, но свойства гармонических чисел мы используем. Средняя длина цепочек с ростом n растет очень медленно, хоть и неограниченно: имея бесконечное время, можно в среднем успеть сделать бесконечное число дел. Не сильно ошибившись, можно сказать, что она растет логарифмически. В свою очередь, дисперсия не сильно отличается от среднего, а добавочный коэффициент H_n,2 стремится к константе π²/6. Немного позже нам пригодится это наблюдение.

На наш вопрос: «Какова вероятность не уложиться в n дней, имея перед собой k последовательных этапов выполнения задачи?» — поможет ответить функция распределения, то есть кумулятивная кривая для распределения Стирлинга. Построим такие кривые для n = 7, 30, 365 и 25 000, соответствующие неделе, месяцу, году и (конечно, условно) всей жизни (рис. 8.3).

Рис. 8.3. Вероятность не успеть выполнить цепочки различной длины в тот или иной срок

Эти графики показывают, что вероятность не уложиться в месяц с заданием, состоящим из пяти шагов, превышает 80 %. Неорганизованному балбесу на неделю лучше не планировать более трех дел, а десяток он не выполнит с вероятностью, превышающей 50 %, и за всю жизнь! Мы убеждаемся в том, что при увеличении сроков на несколько порядков число дел, выполняемых как попало, увеличивается незначительно. Жизнь так коротка!