Бросайте честный кубик, пока не выпадут все шесть сторон; ожидаемое число бросков — 14.7 (первая и вторая ссылки, та же сумма разложенная на множители и раскрытая). Рассуждение в одну строку: пока не хватает k сторон, каждый бросок с вероятностью k/6 новый, так что ожидание следующей новой стороны — геометрическое испытание с математическим ожиданием 6/k, и сумма — 6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6. Третья ссылка выполняет задачу с пятью купонами и получает 11.416666666667. Четвёртая, 6⁶ = 46656, — число возможных последовательностей из шести бросков, неверный инструмент для этого вопроса, но верный знаменатель для родственного: шанс, что первые шесть бросков уже покажут все шесть сторон, — 6!/46 656, едва больше 1.5 процента.
Форма ответа важнее числа: n·H_n растёт как n ln n, так что издержки почти целиком лежат в последних нескольких купонах. Сто штук чего-либо стоят 100·H₁₀₀ = 518.7 попыток, из которых последняя одна даёт сто; первая — единственный бросок. Эта асимметрия — причина того, почему системы бесплатных жетонов ощущаются так, будто буксуют в конце, почему последняя фигурка в наборе коллекционных карточек самая дорогая и почему рандомизированные алгоритмы, которым нужно увидеть каждое значение, платят ту же гармоническую цену. Разброс идёт в ту же сторону: распределение перемасштабированного времени ожидания приближается к закону Гумбеля, у которого длинный правый хвост, так что невезучий собиратель невезуч на большую и предсказуемую величину.
Ответ
14.7
Как его читать
Шесть, умноженное на шестое гармоническое число. Вторая ссылка — та же сумма почленно, третья — пять купонов вместо шести, четвёртая — все последовательности из шести бросков.
Источник
the coupon collector's problem in Feller, 'An Introduction to Probability Theory and Its Applications', volume 1 (1950), where it is posed as the baseball-card question; the expectation n·H_n and the Gumbel limit of the rescaled waiting time are standard
Пересчитать в калькуляторе
Эти ссылки открывают подходящий калькулятор с уже введёнными числами этой задачи. Строка выше — то, что должен показать экран; проверьте сами.