Пример: сбор купонов

Прежде чем переходить к более сложным примерам, рассмотрим еще один тривиальный пример, в котором линейность ожиданий приносит существенную пользу. Предположим, фирма–производитель овсяных хлопьев кладет в каждую коробку купон. Всего существуют n разных видов купонов. Сколько коробок придется купить, чтобы собрать купоны всех типов?

После того, как у вас появятся n – 1 из n видов купонов вероятность того, что новая коробка содержит купон отсутствующего типа, равна всего 1/n.

Следующий метод позволяет точно определить ожидаемое время. Пусть X — случайная переменная, равная количеству коробок, купленных до первого обнаружения купона каждого типа. Как и в наших предыдущих примерах, эта случайная переменная выражается достаточно сложно, и ее было бы удобнее записать в виде суммы более простых случайных переменных.

Для этого рассмотрим следующую естественную идею: процесс сбора купонов продвигается вперед каждый раз, когда вы покупаете коробку с купоном, которого у вас еще нет. Таким образом, основная цель процесса — обеспечить продвижение n раз.

Какова вероятность того, что в заданный момент времени вы добьетесь прогресса на следующем шаге? Это зависит от того, сколько разных типов купонов у вас уже есть. Если у вас уже есть j типов, то вероятность продвижения на следующем шаге составляет (n − j)/n: из n типов купонов n – j позволяют продвинуться вперед.

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

Предположим, процесс сбора купонов находится в фазе j, вы уже собрали купоны j разных типов и ждете возможности получить новый тип. При обнаружении нового типа купона завершается фаза j и начинается фаза j + 1.

Таким образом, процесс начинается в фазе 0 и завершается в фазе n – 1. Пусть Xj — случайная переменная, равная количеству шагов, выполненных в фазе j. Тогда X = X0 + X1 + … +Xn–1, а значит, достаточно найти E[Xj] для каждого j.