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

[ny_quant]

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

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

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

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

Comments

[kdv2005.livejournal.com]

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

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

[ny-quant.livejournal.com]

Маленькая или не маленькая, но моё психологическе восприятие такое, что shuffle у них ни к чёрту.

[kdv2005.livejournal.com]

:-)
то ли прикидка моя никуда не годится, то ли в вычислениях я наврал, но
когда я посчитал точно, то у меня вышло, что вероятность того, что среди 10 наудачу выбранных мелодий (из 200) будет не меньше трех повтороний равна
0.292%
Тогда вероятность того, что это случится хотя бы раз за 250 дней чуть меньше 52%

[kdv2005.livejournal.com]

Виноват, это я в прикидке наврал в одном месте, по ней выходила оценка между 60% и 62%

[ny-quant.livejournal.com]

Давайте я тоже попробую, но по-простому, по рабоче-крестьянски.

Всего возможных пятeрок мелодий для моей утренней программы: N=200^5.

Из них содержат три одинаковые: n=200*199^2~200^3

Вероятность того, что такая дребедень случится сегодня утром p=n/N=1/200^2=0.000025. Соответственно, вероятность того, что этого не не случится P=1-p=1-0.000025=0.999975.

За год у меня бывает 500 поездок (в Вашем варианте 250). Вероятность того, что этого не произойдёт ни разу будет равна P^500 (P^250), т.е. соответственно 0.987578 и 0.993769. Итого вероятность происшедшего 1.2% (0.6%).

Надо полагать наврал где-то с недосыпа.

[kdv2005.livejournal.com]

Я, по рассеянности, все посчитал для десяти мелодий. Нужно было конечно для пятерки.

Саша, Вы неправильно посчитали число пятерок с тремя одинаковыми элементами. Оно на самом деле равно 200*199*198*3*5!/3!= 200*199*198*60
Тогда вероятность того, что три мелодии прозвучать в данное утро приблизительно равна 3/2000, то есть 0.15%. За 500 поездок одна из таких пятерок прозвучит с вероятностью 52.8%

[ny-quant.livejournal.com]

Денис,что-то я не въезжаю насчёт 3*5!/3!. На этом месте, как будто, должен быть биномиальный коэффициент 5!/(3!2!)=10< который я таки пропустил. Тогда ответ получается 11.6%.

Голова, правда, совершенно квадратная, т.к. одновременно смотрю по ночам и хоккей и теннис.

[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%

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

[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%. Как математик, я на лучшее никогда и не рассчитываю :-)

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

[kdv2005.livejournal.com]

1-(1-0.00292...)²⁵⁰=0.5187....

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

[ny-quant.livejournal.com]

http://ny-quant.livejournal.com/128934.html?thread=445606#t445606