Вероятность и статистика · объяснение и практика

Остановка на первом отмеченном предмете при выборе без возвращения

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

Рука ставит оранжевый столбик между двумя синими столбиками разной высоты.

В теме Комбинаторика и пространство исходов · Учебная карта

Главная мысль

В наборе N предметов, из них M отмечены, где 1≤M≤N. Все порядки различимых предметов равновероятны; предметы извлекают без возвращения. Если T — номер первого отмеченного, то P(T=k)=C(N−k,M−1)/C(N,M) при 1≤k≤N−M+1. После N−M неотмеченных предметов следующий успех уже гарантирован, поэтому геометрический закон с постоянным шансом здесь не подходит.

Случайны позиции отмеченных предметов

Можно сначала не различать названия предметов, а указать M позиций отмеченных в перестановке. Каждое подмножество позиций такого размера равновероятно: для него существует одинаковое количество перестановок отмеченных и неотмеченных объектов. Всего C(N,M) вариантов. Чтобы первый отмеченный стоял на позиции k, эта позиция должна быть отмеченной, все предыдущие — свободными от отметки, а остальные M−1 отметок располагаются среди N−k следующих мест.

Так получается числитель C(N−k,M−1). Условие k≤N−M+1 нужно не забыть: после слишком длинного начального блока уже не хватило бы места для всех отметок. Для восьми предметов с тремя отметками первый успех может иметь номера от одного до шести. Седьмой номер невозможен не потому, что его вероятность мала, а потому, что неотмеченных предметов всего пять.

После неудачи состав оставшегося набора меняется

При первом извлечении вероятность отметки равна M/N. Если уже извлечены j неотмеченных предметов, отметок осталось M, а всего предметов N−j. Следующий условный шанс равен M/(N−j) и увеличивается. Это не компенсация случайностью прошлых неудач: физический состав набора действительно изменился. При возвращении предметов состав сохранялся бы, и при независимом новом выборе возникла бы другая модель.

Для вероятности T>k требуется отсутствие отметок на первых k местах. Все M отмеченных позиций должны поместиться среди N−k последних, поэтому P(T>k)=C(N−k,M)/C(N,M) при допустимом целом k. Разность соседних таких вероятностей даёт вероятность точного номера. Можно также перемножить последовательные условные шансы неудачи, каждый раз уменьшая и общий остаток, и число неотмеченных.

Пример

Из десяти предметов четыре отмечены. Какова вероятность, что первый отмеченный окажется третьим?

Успех на третьем месте требует двух неотмеченных, затем отмеченного: (6/10)·(5/9)·(4/8)=1/6. Через позиции получаем C(7,3)/C(10,4)=35/210=1/6. Первые два порядка предметов уже учитываются условным произведением; дополнительный множитель размещений здесь не нужен.

Среднее и гарантированная граница говорят о разном

Средний номер первого отмеченного равен (N+1)/(M+1). Это можно понять через M+1 промежутков неотмеченных: перед первой отметкой, между отметками и после последней. Их распределения симметричны, а общая длина равна N−M. Средняя длина первого промежутка равна (N−M)/(M+1); добавление самой отметки даёт формулу для T. Средний номер обычно дробный, хотя каждый наблюдённый номер целый.

Если отмечены все предметы, T=1 наверняка. Если отметка одна, её позиция равномерна от одного до N и среднее равно (N+1)/2. При M=0 первый успех вообще не существует, поэтому этот случай не включён в формулу. Название отрицательного гипергеометрического закона также встречается для количества неудач T−1: прежде чем сравнивать программы и таблицы, проверьте, что именно считает случайная величина.

От чтения к действию

А теперь — вы

Девять предметов содержат две отметки. Какова вероятность, что в первых трёх извлечениях без возвращения отметок не будет? Все порядки равновероятны.

Частые вопросы

Почему после неудачи шанс растёт, а в независимой модели нет?

Без возвращения число неотмеченных уменьшается при сохранении всех отметок. Это изменение состава, которого нет при независимых испытаниях с постоянным p.

Есть ли конечная гарантированная граница?

Да, при M≥1 первый отмеченный появится не позже номера N−M+1. Это отличается от неограниченной опоры геометрического закона при 0<p<1.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться