Задача про жевачки и вкладыши. Теория вероятностей

[musius]

Здравствуйте!

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

Цитата:

В каждую жевачку вложен один из $n$ вкладышей, причем каждый вкладыш встречается с
вероятностью $1/n$. Сколько в среднем надо купить жевачек, чтобы собрать полную
коллекцию вкладышей?

Вот готовое решение из гугла (я подчеркнул мне непонятный шаг):

Цитата:

Пусть у нас уже собрано $k$ вкладышей. Посчитаем, сколько ждать следующего вкладыша.
Назовем жевачку новой, если вложенный в нее вкладыш не встречается среди $k$ уже
собранных вкладышей. Обозначим $M_k$ среднее количество жевачек, которое нужно
купить, чтобы последняя купленная жевачка была новой. Рассмотрим следующую
купленную жевачку. Она с вероятностью $\frac{n-k}{n}$ новая (и при этом ожидание $(k+1)$-ой
жевачки в коллекции заканчивается), и с вероятностью $\frac{k}{n}$ она не является новой (в этом
случае мы, купив одну жевачку, снова оказываемся в состоянии, когда среднее число
жевачек, которые нужно купить до покупки новой, равно $M_k$). Тем самым, мы приходим к
уравнению $M_k=\frac{n-k}{n}\cdot1+\frac{k}{n}\cdot (M_k + 1)$ (*), откуда $M_k=\frac{n}{n-k}$. Отсюда получаем, что среднее
число жевачек, которое необходимо купить для полной коллекции вкладышей, равно
$M_0 + M_1 + \ldots + M_{n - 1} = \frac{n}{n} + \frac{n}{n-1} + \ldots + \frac{n}{1} = n (1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n})$.

(*) я мог не верно переписать в латех, потому что в оригинале формула была написана так: "Mk=((n-k)/n)*1+(k/n)*(Mk + 1)"
-----------------------
Мои натужные попытки решить это (буду признателен, если укажете мне на мои недочеты):
Обозначим $\xi$ — случайная величина, равная количеству жвачек, которые надо купить, чтобы собрать коллекцию.
Нужно найти $\mathbb{E}\xi$.
$\mathbb{E}\xi = \sum\limits_{i=n}^{\infty} i \cdot \mathbb{P}(\xi = i)$
Значит достаточно найти для каждого $i$ ($i$ равно количеству купленных жвачек) вероятность собрать коллекцию. Вероятность собрать коллекцию равно вероятности собрать $n$ уникальных вкладышей в $i$ испытаниях (т.е. купив $i$ жвачек).

Найдем это так:
$\mathbb{P}(\xi = i) = C_i^n\mathbb{P}_i(\text{собрать n уникальных вкладышей})$ (кол.во способов получить $n$ уникальных из $i$ покупок) (нижний индекс $i$ говорит о том, что происходит $i$ покупок).

$$ \begin{array}{cl} $ & \mathbb{P}_i(\text{собрать n уникальных вкладышей})$\\ $ = & \mathbb{P}_i(\text{купить первый уникальный вкладыш}\cdot\text{купить второй уникальный вкладыш}\cdot \ldots) $\\ $ = & \mathbb{P}_i(\text{удача}_1\cdot\text{удача}_2\cdot \ldots) $\\ $ = & \mathbb{P}_i(\text{удача}_1)\cdot\mathbb{P}_i(\text{удача}_2 | \text{удача}_1)\cdot\mathbb{P}_i(\text{удача}_3|\text{удача}_1\text{удача}_2)\cdot\ldots$ \end{array} $$

$$ \begin{array}{ll} $ \mathbb{P}_i(\text{удача}_1) &= 1 \quad \text{(потому что на руках нет вкладышей и все считаются уникальными)} $ \\ $ \mathbb{P}_i(\text{удача}_2 | \text{удача}_1) &= 1 \cdot \frac{n-1}{n} \quad \text{(есть n-1 уникальных из всей массы вкладышей)} $ \end{array} $$

Получается так: $ \mathbb{P}_i(\text{удача}_{k+1} | \ldots) = \frac{n-k}{n} $ и $\mathbb{P}_i(\text{собрать n уникальных вкладышей}) = \frac{n}{n}\frac{n-1}{n}\frac{n-2}{n}\frac{n-3}{n}\ldots\frac{1}{n}$ = $\frac{n!}{n^n}$.

Тогда $\sum\limits_{i=n}^{\infty} i \cdot \mathbb{P}(\xi = i) = \sum\limits_{i=n}^{\infty} i \cdot C_i^n \frac{n!}{n^n} = \sum\limits_{i=n}^{\infty} i \cdot \frac{i!}{n^n (i-n)!}$

Но это какая-то жесть. Я не понимаю технологии рассуждений в таких задачах. Понимаю, что сейчас излишне формализовал свое решение и сам запутался. Попыток решения этой задачи у меня наверное три. И все три с разными ответами.

[gris]

Начните с более простого. Сколько раз в среднем надо подкинуть монетку, чтобы в истории выпадений были обе стороны. Сколько раз в среднем надо вынуть из колоды карту (с возвратом), чтобы увидеть все масти. Поразбирайте частные случаи, а потом перейдёте к общему.

[musius]

gris в сообщении #982347 писал(а):

Начните с более простого. Сколько раз в среднем надо подкинуть монетку, чтобы в истории выпадений были обе стороны. Сколько раз в среднем надо вынуть из колоды карту (с возвратом), чтобы увидеть все масти. Поразбирайте частные случаи, а потом перейдёте к общему.

Спасибо. Сейчас попробую

[--mS--]

Не понимаю одного: почему не воспользоваться (вместо решения влоб и рекуррентных соотношений) стандартным рассуждением, просуммировав случайные величины - время ожидания первого нового вкладыша ($=1$), второго нового вкладыша, третьего и т.д., а затем их математические ожидания? Время измеряется количеством купленных жевательных резинок, величины с геометрически распределением, матожидание известно.

[musius]

--mS-- в сообщении #982490 писал(а):

Не понимаю одного: почему не воспользоваться (вместо решения влоб и рекуррентных соотношений) стандартным рассуждением, просуммировав случайные величины - время ожидания первого нового вкладыша ($=1$), второго нового вкладыша, третьего и т.д., а затем их математические ожидания? Время измеряется количеством купленных жевательных резинок, величины с геометрически распределением, матожидание известно.

gris в сообщении #982347 писал(а):

Начните с более простого. Сколько раз в среднем надо подкинуть монетку, чтобы в истории выпадений были обе стороны. Сколько раз в среднем надо вынуть из колоды карту (с возвратом), чтобы увидеть все масти. Поразбирайте частные случаи, а потом перейдёте к общему.

Спасибо, получилось

[dmittov]

Помню эту задачу с университетского курса. Она состояла из 2х частей:
1) Посчитать мат ожидание.
2) Сколько жвачек нужно купить, чтобы вероятность собрать коллекцию была 80% ?

Именно со второй частью не могу понять что делать. Помню, что не сложно, но что именно нужно применить...

[--mS--]

Оценить грубо по неравенству Маркова.

[Ingran]

Задача про коллекцию разобрана довольно подробно вот тут. http://habrahabr.ru/post/274803/