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

[ny_quant]

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

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

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

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

Comments

[kdv2005.livejournal.com]

Подсчитаем количество пятерок, которые можно составить из 200 элементов так, чтобы один элемент в такой пятерке повторялся трижды. Я, кстати, тоже проврался в решении, так что заодно ее исправлю и свою оплошность.

Вначале рассмотрим ситуацию, когда в пятерке прозвучали три мелодии, и одна из них прозвучала ровно три раза. Из 200 элементов можно выбрать 200*199*198/6 =1313400 троек. В каждой тройке можно тремя способами выбрать повторяющуюся мелодию. Пусть в тройке {A,B,C} мелодия А повторяется 3 раза, а B и C --- по одному разу. Пятерку символов AAABC можно упорядочить 5! способов, но перестановки символов А между собой не меняют порядка, поэтому число различных упорядочений этих символов равно 5!/3!
Стало быть, всего существует (200*199*198/6)*3*(5!/3!)=78804000 упорядоченных пятерок из трех мелодий, в которой одна из них повторяется трижды, а две другие по разу (это число приблизительно равно 10*200³).

Аналогично можно подсчитать общее число пятерок из двух мелодий, из которых одна повторяется трижды, а другая дважды.
Оно равно (200*199/2)*2*(5!/3!2!)=398000, то есть, приблизительно 10*200².

Тем самым, вероятность пятерки с трижды повторяющейся мелодией приблизительно равна 10*200³/200⁵, то есть, 1/4000 или 0.025% (если точно, то .024750625%)

За пятьсот поездок получаем вероятность того, что одна мелодия прозвучит трижды порядка 1/8 (если точно, то 11.64%)
Ну вот, теперь, кажется, все сошлось.

[ny-quant.livejournal.com]

Теперь сошлось.

А мне такие задачи приходится иной раз на интервью за 5 минут решать. Вроде бы и ничего сложного, но провраться, как мы сейчас наглядно показали, проще простого.

Особенно опечалило полное отсутствие интуиции. Ведь не на один, а на два порядка ошиблись. Во где стыдоба-то!

[kdv2005.livejournal.com]

С комбинаторикой всегда провраться несложно. Если можно, лучше всегда пользоваться пуассоновским приближением. Оно кстати, в этом случае тоже вполне неплохо себя проявляет:

по пуассоновскому приближению
вероятность того, что данная мелодия прозвучит три раза из пяти равна
(1/3!) * (1/40)³ e^-1/40,
отбрасывая экспоненту и домножая на 200 получаем оценку вероятности того, что хотя бы одна мелодия прозвучит трижды:
1/1920, то есть приблизительно 0.05%.
Нагрубили, конечно, но это оценка сверху, так, что не страшно. За 500 поездок в среднем такое будет происходить около четверти раза. Значит можно снова воспользоваться пуассовским приближением: 1-e^-1/4
-- где-то около 20%