Вероятность и статистика · объяснение и практика
Почему последние недостающие типы увеличивают ожидание полного набора
Разложите сбор полного равновероятного набора на этапы ожидания нового типа и объясните, почему последние типы требуют больше попыток.

В теме Случайные величины и распределения · Учебная карта
Главная мысль
Для n равновероятных типов при независимых выборах с возвращением ожидаемое число попыток до полного набора равно n(1+1/2+…+1/n). Уже встреченные повторы тоже входят в число попыток.
Успех этапа — появление нового типа
Коллекционер независимо получает один из n типов, все типы равновероятны. После k разных собранных типов вероятность нового равна (n−k)/n. Число попыток до следующего нового типа имеет геометрическое ожидание n/(n−k). При k=0 первая попытка всегда приносит новый тип, а перед последним типом шанс равен лишь одной n-й.
Полное время — сумма длительностей этапов от нуля собранных до полного набора. Линейность ожидания позволяет сложить средние этих этапов: n/n+n/(n−1)+…+n/1. Получается nHₙ. Для этого сложения не требуется отдельно доказывать независимость длительностей; важно правильно определить распределение ожидания на каждом этапе в исходной независимой модели выборов.
Последний пробел в коллекции дорог
Для четырёх типов ожидание равно 1+4/3+2+4=25/3. Последний этап в среднем требует четыре попытки, тогда как самая первая попытка гарантированно полезна. Поэтому линейная догадка «четыре типа — значит примерно четыре попытки» игнорирует накапливающиеся повторы. Среднее может быть дробным, хотя время завершения целое.
Завершение не имеет конечного гарантированного срока: при любом числе попыток существует положительная вероятность долго получать уже собранные типы. В то же время полный набор собирается почти наверное и имеет указанное конечное ожидание. Вероятность один не равна гарантии уложиться в заранее назначенное конечное число шагов.
Пример
Для трёх равновероятных типов найдите ожидаемое число попыток до полного набора.
Этапы имеют средние 1, 3/2 и 3. Их сумма 11/2=5,5. Число 3 — минимально возможное время, но не математическое ожидание с учётом повторов.
Неравные вероятности требуют другой суммы
Если типы имеют разные вероятности, шанс нового зависит не только от числа уже собранных, но и от того, какие именно типы остались. Тогда простая гармоническая формула не применяется. Очень редкий тип способен определять почти всё ожидание, а тип с нулевой вероятностью вообще делает полный сбор невозможным.
Выбор без возвращения из готового набора — другая задача: повторов может не быть, и после каждого выбора состав доступных объектов меняется. Перед вычислением следует назвать механизм пополнения, число типов и равномерность. Формула описывает идеальную вероятностную модель, а не обещает срок получения реальных карточек при неизвестных долях производства и зависимых упаковках.
От чтения к действию
А теперь — вы
Частые вопросы
nHₙ — гарантированное количество попыток?
Нет. Это ожидание. Возможны и быстрое завершение без повторов, и существенно более длинное ожидание, без конечного гарантированного срока.
Что меняется при неравных вероятностях типов?
Нужно учитывать конкретный набор отсутствующих типов. Одного числа уже собранных недостаточно для вероятности нового, поэтому простая формула не действует.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как посчитать номер попытки заданного по счёту успеха
Найдите вероятность номера попытки заданного успеха, выделив обязательный успех в конце и расположения предыдущих успехов.
Открыть темуПочему совпадение дней рождения зависит от числа пар
Вычислите вероятность любого совпадения через дополнение к случаю всех разных и отличите её от совпадения с одним заранее названным днём.
Открыть тему