Coupon collector's problem (generating function approach)
||It has been suggested that this article be merged into Coupon collector's problem. (Discuss) Proposed since August 2011.|
This technique uses the probability generating function (PGF) where is the probability that q steps are taken to collect the n coupons i.e.
and the expectation is given by
can be calculated explicitly as follows :
In this equation, It can be found some features :
This is the PGF of an event that has probability p occurring zero or more times, with the exponent of z counting the number of times. We split the sequence of coupons into segments. A new segment begins every time a new coupon is retrieved for the first time. The PGF is the product of the PGFs of the individual segments.
Applying this to , It represents the following sequence of events:
- retrieve the first coupon (no restrictions at this time)
- retrieve the first coupon some number of times
- retrieve the second coupon (probability )
- retrieve a mix of the first and second coupons some number of times
- retrieve the third coupon (probability )
- retrieve a mix of the first, second, and third coupons some number of times
- retrieve the fourth coupon (probability )
- retrieve the last coupon (probability ).
In the following, and denote harmonic numbers.
The function , first simplified before deriving the expectation, can be expressed as follows :
In this function, the following formula can be used to obtain the derivative of :
From this equation, it can be found as following :
The next formula is useful for simplifying the :
The PGF makes it possible to obtain an exact value for the variance.
This formula consists entirely of factorial moments that can be calculated from the PGF. The value of is already found.
The remainder can be calculated as follows :
This derivative is
Evaluation at yields
As all value has been found, the conclusion can be reached at the following: