Экзамен ААА — Случайный подарок: вероятность дотянуть до конца

Условие

В пяти ближайших магазинах приготовили подарки для Пети, который участвует в квартирной игре с подарочными коробочками. В магазине покупки оформляют коробку с подарком, в каждом — по одному подарку. На каждый подарок выпала разная вероятность p_1, …, p_5. Петя посещает магазины случайно (равновероятно):

• При первом посещении магазина (если коробка не открыта) — кладёт в неё подарок с вероятностью p_i.
• На втором заходе (если коробка открыта) — пробует поправить, повышая шанс на подарок ещё на p_i (предположительно).
• Игра продолжается, пока во всех пяти магазинах не появятся подарки.

Внутри одной коробки в один момент Петя оказывается равно с вероятностью 1/5 каждой.

Задача

1. Вычислить вероятность, что Петя получит подарок в каждой из 5 коробок.
2. Можно вывести точную формулу при равных p_i = p.

Параметры

n = 5, p_i известны (например, p_i = 0.4 для всех).

Решение

Подход — задача о коллекционере купонов

Это вариация Coupon Collector: после случайных посещений магазинов с шансом p каждого «открытия» подарка нужно дождаться, чтобы все 5 были открыты.

Простой случай — равные p_i = p

Пусть T_k — число посещений до того, как стало k+1 открытых коробок при k уже открытых. На каждом посещении:

• С вероятностью (5 − k)/5 мы зашли в неоткрытую коробку → с вероятностью p она открывается.
• С вероятностью k/5 зашли в открытую — ничего нового.

Эффективная вероятность открыть на одном шаге = (5 − k)/5 · p. Значит T_k ~ Geom(λ_k) с λ_k = (5 − k) p / 5.

Матожидание времени до открытия всех 5:

E[T] = Σ_{k=0..4} 1 / λ_k = (5/p) · Σ_{k=0..4} 1/(5 − k) = (5/p) · H_5

где H_5 = 1 + 1/2 + 1/3 + 1/4 + 1/5 = 137/60 ≈ 2.283.

При p = 0.4: E[T] = (5 / 0.4) · 137/60 = 12.5 · 2.283 ≈ 28.5 посещений.

Вероятность завершить за N посещений

Это уже более тонкая задача. Используем включения-исключения:

P(все 5 открыты после N посещений) = Σ_{k=0..5} (-1)^k C(5, k) · (1 - kp/5)^N

При p = 1 это формула «вероятность все купоны собраны»: Σ (-1)^k C(5, k) (1 − k/5)^N.

Случай различных p_i

При различных p_i строим марковскую цепь с состояниями = подмножествами открытых коробок (всего 2^5 = 32 состояний). Переходы: из состояния S (открытые) при посещении магазина i:

• Если i ∈ S — состояние не меняется.
• Если i ∉ S — с вероятностью p_i переходим в S ∪ {i}, иначе остаёмся.

Каждый шаг: магазин выбирается равновероятно из 5.

import numpy as np
from itertools import combinations
 
def simulate(p_list, n_iter=200_000, max_steps=10_000):
    successes = 0
    for _ in range(n_iter):
        opened = [False] * 5
        steps = 0
        while not all(opened) and steps < max_steps:
            i = np.random.randint(5)
            if not opened[i] and np.random.random() < p_list[i]:
                opened[i] = True
            steps += 1
        if all(opened):
            successes += 1
    return successes / n_iter
 
print(simulate([0.4]*5, n_iter=100_000))

Аналитика для разных p_i

Используем систему линейных уравнений для матожидания:

Обозначим E[S] — матожидание числа шагов из состояния S до состояния {1, 2, 3, 4, 5}.

E[S] = 1 + (1/5) Σ_{i=1..5} [
    p_i · E[S ∪ {i}]  +  (1 − p_i) · E[S]      если i ∉ S
    E[S]                                         если i ∈ S
]

Решаем рекурсивно от E[full] = 0.

def expected_steps(p_list):
    n = len(p_list)
    E = {(1 << n) - 1: 0.0}
    for size in range(n - 1, -1, -1):
        for S in combinations(range(n), size):
            mask = sum(1 << i for i in S)
            denom = 1 - (1/n) * sum(
                (1 - p_list[i]) if not (mask & (1 << i)) else 1
                for i in range(n)
            )
            num = 1 + (1/n) * sum(
                p_list[i] * E[mask | (1 << i)]
                for i in range(n) if not (mask & (1 << i))
            )
            E[mask] = num / denom
    return E[0]

Подводные камни

1. «Можно вывести при равных p» — Coupon Collector. Чёткое узнавание паттерна H_n / p экономит время.
2. «Магазин выбирается равновероятно». Без этого условия задача меняется радикально.
3. «На втором заходе». В условии есть нюанс — подарок «дополнительно повышается» на p_i. Это не то же самое, что стандартный Coupon Collector. Уточняйте: либо это всё-таки геометрика, либо нужно строить цепь Маркова с состояниями (открыта/неоткрыта/повторно)?
4. Включения-исключения для P(собрано за N). Не путать с E[T].
5. H_n — гармоническое число. H_5 = 137/60. На экзамене стоит уметь записать в общем виде.
6. 2^n состояний для случая разных p_i — полиномиально только при малом n.

Эталонный ответ

Сценарий с равными p_i = p:

• E[T] = (n/p) · H_n (матожидание числа посещений).
• P(все собраны за N посещений) = Σ_{k=0..n} (-1)^k C(n, k) (1 − kp/n)^N.

При n = 5, p = 0.4: E[T] ≈ 28.5.

Сценарий с разными p_i: марковская цепь на 2^n состояниях с системой линейных уравнений или прямая симуляция Монте-Карло.