сумма (математическое)
Mar. 1st, 2010 05:18 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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...
Тот же вопрос строгим языком: каково матожидание числа попыток, после которого сумма всех значений станет больше 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...
