Ни о какой безапелляционности в моих высказываниях не может быть и речи!

Выберем наугад число, лежащее между 0 и 1. Потом еще раз выберем, и добавим к первому. Потом еще раз, и добавим к сумме до сих пор. И так далее. Сколько в среднем раз нам надо будет выбирать, пока сумма не станет больше 1?

Тот же вопрос строгим языком: каково матожидание числа попыток, после которого сумма всех значений станет больше 1?

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



Сначала ответим на вопрос: какова вероятность того, что за n попыток мы не добьемся успеха, т.е. не перейдем 1?
Пусть x₁, x₂,... x_n - независимые случайные переменные, распределенные равномерно между 0 и 1. Пусть S_n - сумма первых n из них; тогда мы спрашиваем, чему равна вероятность, что S_n не переходит 1, Pr(S_n<1)?

Можно вычислить это индуктивно, задав более общий вопрос, чему равна Pr(S_n<t), через простые интегралы. Но я хочу показать красивый трюк, благодаря которому никакие интегралы вычислять вообще не надо.

Обозначим через y_n дробную часть суммы S_n (можно это записать как y_n = S_n mod 1). Каждая из y_n - случайная переменная со значениями между 0 и 1. Покажем, что y_n, как и исходные x_n, распределены независимо и равномерно. Достаточно для этого показать, что значение (x₁+x₂) mod 1 распределено равномерно и не зависит от x₁, остальное очевидно по индукции. Чтобы увидеть, что значение дробной части x₁+x₂ равномерно от 0 до 1, достаточно картинки:



Здесь для примера заштрихованы участки, в которых y₂, т.е. дробная часть x₁+x₂, меньше 0.2. Наглядно видно, что для любого конкретного значения x₁, если в нем провести вертикальную линию, то она будет заштрихованной на 0.2 своей длины. То же самое для x₂ и любой горизонтальной линии. Отсюда сразу ясно, что общая площадь заштрихованных участков, т.е. вероятность Pr(y₂ < 0.2), равна 0.2; то есть y₂ распределена равномерно. Отсюда также видно, почему значение y₂ не зависит от значения x₁. Например, если ограничить x₁ < 0.5, или какими-то другими значениями, все равно заштрихованные участки будут занимать 0.2 от всей возможной площади для данных значений x₁.

Теперь - ключевое наблюдение: сумма S_n не превышает 1 тогда и только тогда, когда y₁ < y₂ < ... < y_n.

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

Но раз переменные y₁...y_n распределены равномерно и независимо, любой порядок между их значениями столь же вероятен, как любой другой порядок. Всего возможных порядков, т.е. перестановок из n чисел - значений y₁...y_n - имеется n!. И только один из них, а именно y₁ < y₂ < ... < y_n, соответствует случаю, когда сумма исходных переменных меньше 1. Поэтому вероятность этого события, Pr(S_n<1), равна 1/n!. Это и есть красивый трюк, который я хотел показать.

Осталось объяснить, как отсюда придти к матожиданию числа слагаемых. Это число равно n в том случае, когда сумма n-1 первых переменных еще меньше 1, а сумма n уже перешла 1. Т.е. нам нужно из события "S_n > 1" исключить все случаи, когда верно событие "S_n-1 > 1"; но поскольку это второе всегда влечет за собой первое, то "все такие случаи внутри события S_n > 1" это то же самое, что "все такие случаи" вообще. Поэтому нам всего лишь надо вычесть Pr(S_n > 1) - Pr(S_n-1 > 1), что получается

(1 - 1/n!) - (1 - 1/(n-1)!) = 1/(n-1)! - 1/n! = 1/(n*(n-2)!)

Это вероятность того, что сумма перейдет 1 за ровно n попыток. Чтобы вычислить матожидание числа попыток, надо теперь посчитать сумму всех n*"вероятность того, что попыток ровно n", т.е. в данном случае, посчитать сумму 1/(n-2)! по всем n, начиная с n=2. Это то же самое, что сумма 1/n! по всем n, начиная с 0, что, как известно, равно числу e, 2.71828...