Question

Problem 1: Coupon Collector Problem Gary Oak is on a mission to complete his Pokedex before Ash Ketchum. To this end, he starts searching the tall grass for Pokemon. Assume that there are m Pokemon in total and that Gary has seen none of them at the start. Assume also, that all of the m Pokemon are equally likely to appear in the tall grass and each appearance is independent of the previous appearances. Let K be the number of encounters required for Gary to fill his Pokedex (A filled Pokedex means that he has seen all m Pokemon atleast once). Find the expectation and variance of K. Hint: Find the expected number of encounters to find a new Pokemon having already seen k(say) Pokemon and use this to find the required quantities.

Problem 1: Coupon Collector Problem
Gary Oak is on a mission to complete his Pokedex before Ash Ketchum. To this end, he starts
searching the tall grass for Pokemon. Assume that there are m Pokemon in total and that Gary
has seen none of them at the start. Assume also, that all of the m Pokemon are equally likely to
appear in the tall grass and each appearance is independent of the previous appearances. Let K
be the number of encounters required for Gary to fill his Pokedex (A filled Pokedex means that he
has seen all m Pokemon atleast once). Find the expectation and variance of K.
Hint: Find the expected number of encounters to find a new Pokemon having already seen k(say)
Pokemon and use this to find the required quantities.

Answer 1

Let T be the time to collect all n coupons, and let t, be the time to collect the i-th coupon after - 1 coupons have been collected. Think of Tand t, as random variables. Observe that the probability of collecting a new coupon is p, = (n-(1-1))/n. Therefore, t, has geometric distribution with expectation 1/p,. By the linearity of expectations we have: PI P2 --+음+ " (1小 + n + !) VL TL

To find its variance: Variance Var(Xi X2+... . XN) - A1Var(X,) (since X1, X2,X3 ...are all independent to each other) E(X) E(X)2, In case of Xi: VarXi probability that the ith type of coupon would be observed in the next try is Pi (n-i + 1)/n (we have already seen 1-1 coupons out of a total of n coupons) to calculate E(Xi), observe that with probability pi, expected number of coupons required-1 (success in the first try) and with probability 1p;expected number of coupons required E(Xi +1) (one trial wasted, we would again need E(Xi) expected coupons) E(X) = pi + (1-Pi)2(X, + 1) E(X) = 1/A by the same reasoning for E(X2 Variance = Σ 1 (1-Pi)