Random Variables · Linearity of Mathematical Expectation

Lesson 11

Nikolai Chukhin · Alexander S. Kulikov

In a more general formulation, this problem is known as the coupon collector problem, which is used to analyze various games: there are \(n\) types of coupons, and each purchase gives you a random type of coupon; how many coupons on average must you buy to collect all of them?

For analysis, the idea of segments, which we used when considering the problem of the expected waiting time for the first six to appear, will help. Let our coupons be numbers from \([n]\), and we write down the received coupons in a row. Insert a line break after each new type of coupon. 

from random import randint, seed

seed(17)

seen = set()
while len(seen) < 6:
    x = randint(1, 6)
    print(x, end=' ' if x in seen else '\n')
    seen.add(x)

5
4
3
3 3 2
6
6 5 6 3 1
The length of each such segment is a random variable. Denote them by \(\alpha_{1}, \dotsc, \alpha_{n}\). Then we need to find \[\operatorname{E}[\alpha_{1}+\dotsb+\alpha_{n}] \ .\] This, of course, reduces to finding \(\operatorname{E}[\alpha_{i}]\). \(\operatorname{E}[\alpha_{i}]\) is the average length of the \(i\)-th segment, i.e., the segment ending with the \(i\)-th new coupon. When filling this segment, there are \(i-1\) coupons that are not new and \(n-i+1\) coupons that have not yet appeared. That is, the probability of encountering a new coupon at each step (when filling the \(i\)-th segment) is \(\frac{n-i+1}{n}\). Therefore, \(\operatorname{E}[\alpha_{i}]\) is simply the expected waiting time for the first success, where at each step success occurs with probability \(\frac{n-i+1}{n}\). Consequently, \[\operatorname{E}[\alpha_{i}]=\frac{n}{n-i+1}\ .\] This corresponds to reality: the larger \(i\), the greater this expectation. Thus, the required expectation is estimated as \[\sum_{i=1}^{n}\frac{n}{n-i+1}=n\sum_{i=1}^{n}\frac{1}{i}=nH_{n} \approx n (\ln n + \gamma) \ ,\] where \(H_{n}=\sum_{i=1}^{n}\frac{1}{i}\) is the harmonic number, and \(\gamma=\lim_{n \to \infty}(H_{n}-\ln n)\approx 0.577\) is the Euler-Mascheroni constant.