Генератор (не)случайных чисел.

[ny_quant]

Проверка интуиции.

У меня в телефоне примерно 200 мелодий. Каждый день по дороге на работу и с работы я успеваю прослушать 10 (5+5). Делаю это на протяжении примерно года. Плэйер установлен на игру в случайном порядке. Сегодня по дороге на работу одна и та же песня выскочила у меня три раза. Нет ли в телефоне проблемы с генератором случайных чисел?

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

Мне кажется, вероятность такого явления порядка 0.1%.

Comments

[kdv2005.livejournal.com]

У меня тоже по прикидке 0.1%. А точно считать лень.
Ответ можно найти в Гугле по ключевым словам matching birthday problem,
triple matches

Но вероятность 1/1000 совсем не маленькая, если уж говорить о психологическом восприятии: бросить 10 раз монетку и все орлом,
бросить четыре кости и получить все шестерки -- понятно, что будет сюрприз, но не такой уж невообразимый.

Вот мое рассуждение

[kdv2005.livejournal.com]

Выберем какую-нибудь мелодию. Тогда вероятность того, что она будет выбрана в данный конкретный раз (в предположении, что генератор действительно случайный и равномерный) равна 1/200. Это очень редкое событие, поэтому вероятность того, что данная мелодия прозвучит трижды может быть вычислена с помощью пуассоновского приближения. Какова вероятность того, что сумма десяти независимых пуассоновских величин с параметром 1/200 примет значение 3? Эта сумма имеет пуассоновское распределение с параметром 1/20, поэтому вероятность равна (1/3!)*(1/20)³*e^-1/20. Oтбрасывая экспоненциальный множитель получаем 1/(48*10^3), то есть приблизительно 0.002%.

Поскольку мелодий всего 200, то вероятность того, что хотя бы одна из них прозвучит трижды, оценивается сверху величиной 200*0.002%, то есть 0.4%. Эта оценка несколько завышена: если вычислить вероятность точно, без пуассоновского приближения, то получится
936 694 814 640 883/(32*10¹⁶), что дает 0.292...%.

Если вероятность того, что событие произойдет сегодня, равна 0.4%,
то за 250 дней оно в среднем произойдет 1 раз. Это означает, что для вычисления вероятности того, что оно произойдет хотя бы раз за 250 дней можно снова воспользоваться пуассоновским приближением. Вероятность того, что пуассоновская величина с параметром 1 принимает положительное значение равна 1-е^-1, то есть приблизительно 63% или 2/3.
Tочное вычисление дает
1-(1-0.00292...)250=0.5187....
Погрешность оценки порядка 20%. Как математик, я на лучшее никогда и не рассчитываю :-)