Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

сумма (математическое)

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

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

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



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

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

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



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

Теперь - ключевое наблюдение: сумма Sn не превышает 1 тогда и только тогда, когда y1 < y2 < ... < yn.

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

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

Осталось объяснить, как отсюда придти к матожиданию числа слагаемых. Это число равно n в том случае, когда сумма n-1 первых переменных еще меньше 1, а сумма n уже перешла 1. Т.е. нам нужно из события "Sn > 1" исключить все случаи, когда верно событие "Sn-1 > 1"; но поскольку это второе всегда влечет за собой первое, то "все такие случаи внутри события Sn > 1" это то же самое, что "все такие случаи" вообще. Поэтому нам всего лишь надо вычесть Pr(Sn > 1) - Pr(Sn-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...
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 26 comments