?

Log in

сумма (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

сумма (математическое) [мар. 1, 2010|05:18 pm]
Anatoly Vorobey
Выберем наугад число, лежащее между 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...
СсылкаОтветить

Comments:
[User Picture]From: timur0
2010-03-01 03:29 pm
Это верно потому, что пока сумма остается больше единицы,

- меньше
(Ответить) (Thread)
[User Picture]From: avva
2010-03-01 03:31 pm
ага, спасибо.
(Ответить) (Parent) (Thread)
[User Picture]From: rezoner
2010-03-01 03:40 pm
А нельзя проще, исходя из среднего биномиального распределения? Сразу у меня что-то не получается, но я попробую попозже.
(Ответить) (Thread)
[User Picture]From: antchi
2010-03-01 04:18 pm
А где там биномиальное?
(Ответить) (Parent) (Thread)
[User Picture]From: rezoner
2010-03-01 04:24 pm
ААААААААААААААААААААААААА!!!!!!!!!

Я идиот. "Выберем наугад число между 0 и 1" прочитал как "из нуля и единицы. Спасибо :))
(Ответить) (Parent) (Thread)
[User Picture]From: muchkap
2010-03-01 03:44 pm
спасибо! а ответ как-нибудь масштабируется на случай если выбирать целые числа от 0 до 100?
(Ответить) (Thread)
[User Picture]From: dopkins
2010-03-02 08:23 am
Число попыток не зависит от длины интервала.
(Ответить) (Parent) (Thread)
[User Picture]From: dopkins
2010-03-02 08:26 am
Упс, не учёл, что числа целые. Но важно, что масштабирования нет.
(Ответить) (Parent) (Thread)
[User Picture]From: muchkap
2010-03-02 08:35 am
спасибо, проверю в экселе)
(Ответить) (Parent) (Thread)
[User Picture]From: kzn
2010-03-01 03:47 pm
Возможно дурацкий вопрос - а нельзя ли для этой задачи использовать центральную предельную теорему?
(Ответить) (Thread)
[User Picture]From: falcao
2010-03-01 04:03 pm

impressive

Очень вкусное решение! Приём с дробными частями впечатляет!

В самом конце у Вас опечатка: там из меньшего числа вычитается большее, а должно быть наоборот.
(Ответить) (Thread)
[User Picture]From: avva
2010-03-01 04:51 pm

Re: impressive

Спасибо, исправил уравнение.
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2010-03-01 05:10 pm
Спасибо! Не знал такого красивого решения. Буду использовать.
(Ответить) (Thread)
[User Picture]From: etre_moral
2010-03-01 05:12 pm
Трюк хороший, но и без трюка это вроде как очевидно: вероятность того, что сумма меньше единицы, это объём соответствующего симплекса \{x_i>0, x_1+\ldots+x_n<1\}, то есть 1/n! (рёбра равны единице и перпендикулярны).
(Ответить) (Thread)
[User Picture]From: buddha239
2010-03-01 05:42 pm
+1.
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2010-03-01 06:05 pm
А объем симплекса именно такой, потому что из n! симплексов собирается единичный куб. Тот же трюк, только в профиль :)
(Ответить) (Parent) (Thread)
[User Picture]From: etre_moral
2010-03-01 06:39 pm
Ну это кто как хочет доказывать... :)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2010-03-01 08:14 pm
Или теми же интегралами :)
(Ответить) (Parent) (Thread)
[User Picture]From: janatem
2010-03-01 06:00 pm
Ё, я такой умный, когда нетрезвый: пока читал условие (не заглядывая под кат), угадал, что ответ должен быть равен e. (Позже попытаюсь проанализировать, почему я так подумал.)
(Ответить) (Thread)
[User Picture]From: avva
2010-03-01 08:15 pm
Да, я тоже угадал, когда решал. Это довольно логично. Ясно, что не может быть 2, потому что нужно не меньше 2 попыток; но если средняя попытка 0.5, то и сильно больше 2 не может быть.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2010-03-01 06:35 pm
вариант: бросаем n-стороннюю игральную кость, пока сумма выпавших очков не превысит n. каково матожидание количества бросков?
(Ответить) (Thread)
[User Picture]From: f137
2010-03-01 08:05 pm
Про e помню еще из Гарднера, а вот за вывод - спасибо!
(Ответить) (Thread)
From: (Anonymous)
2010-03-03 10:42 am
почему иксы распределены равномерно?
(Ответить) (Parent) (Thread)
From: ionial
2010-03-18 08:40 pm

а теперь новая задача - обобщить это для k<n

то есть, какое мат-ожидание числа слагаемых, чтобы сумма перешла k<=n.
я, пока, сумел только для посчитать вероятность того, что сумма < 2 :-(
(Ответить) (Thread)
[User Picture]From: knop
2010-04-29 04:46 am

Re: а теперь новая задача - обобщить это для k<n

А разве не очевидно, что это k*e попыток?
(Ответить) (Parent) (Thread)
From: ionial
2010-04-29 07:59 am

Re: а теперь новая задача - обобщить это для k<n

Между очевидно и доказуемо есть разница, не так ли?
(Ответить) (Parent) (Thread)