Probability theory and stochastic processes Combinatorial and geometric probability Problem

Coupon collector's problem

Builds on Geometric distribution Linearity of expectation Mean of the geometric distribution Variance of a sum of independent random variables

Problem

There are $n \ge 1$ different types of coupons. Each draw gives a coupon of a uniform random type, independently of the other draws. Let $T$ be the number of draws needed to collect all $n$ types. Find $E[T]$ .

Remarks

Solution: write $T = t_1 + \dots + t_n$ , where $t_i$ is the number of draws to get a new type when $i - 1$ types are known. Each $t_i$ counts trials up to the first success, with success probability $p_i = (n - i + 1)/n$ . So $E[t_i] = 1/p_i$ by the mean of the geometric distribution. By linearity of expectation, $E[T] = n \left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n}\right) = n H_n$ , where $H_n$ is the $n$ -th harmonic number. So $E[T] = n \ln n + \gamma n + \frac{1}{2} + o(1)$ , with the Euler–Mascheroni constant $\gamma \approx 0.5772$ . The $t_i$ are independent, so $\operatorname{Var}(T) = \sum_i (1 - p_i)/p_i^2 < \pi^2 n^2 / 6$ .

Reading path

To understand this page from the ground up, read these 68 pages in order. The foundations come first.

Construction of the reals from Cauchy sequences concept
Element definition
Integers object
Ordered field definition
Proposition concept
Random experiment concept
Rational numbers object
Real numbers object
Set definition
Ring of integers statement
Disjunction definition
Implication definition
Predicate definition
Bernoulli trial concept
Ordered pair definition
Union definition
Sample space definition
The rationals form a field statement
Existential quantifier definition
Universal quantifier definition
Cartesian product definition
Subset definition
The rationals form an ordered field statement
Uniqueness quantifier definition
Binary relation definition
Universal set definition
Order on the reals definition
Power set definition
Complement definition
Function definition
Interval definition
Injective function definition
Preimage of a set definition
Sigma-algebra definition
Countable set definition
Event definition
Borel sigma-algebra definition
Probability axioms concept
Probability measure definition
Probability distribution definition
Probability space definition
Conditional probability definition
Random variable definition
Cumulative distribution function definition
Discrete random variable definition
Law of a random variable definition
Independence of two events definition
Random variable with a density definition
Joint probability distribution definition
Probability mass function definition
Mutual independence of events definition
Expected value definition
Independence of two random variables definition
Marginal distribution definition
Tail sum formula for expectation statement
Independent sigma-algebras definition
Variance definition
Geometric distribution definition
Linearity of expectation statement
Independence means the joint law is the product of the marginals statement
Independence of random variables definition
Mean of the geometric distribution statement
Covariance definition
Expectation of a product of independent random variables statement
Variance of a sum statement
Independent random variables are uncorrelated statement
Variance of a sum of independent random variables statement
Coupon collector's problem problem

Tag	`0MXCP7MXWJ`
URI	`m2://0MXCP7MXWJ`
Aliases	`coupon-collector-problem`
Kind	problem
Writing	W0 stub
MSC	60C05
Status	This copy of the site has no build data. Run `m2 status 0MXCP7MXWJ`.
Uses	Geometric distribution, Linearity of expectation, Mean of the geometric distribution, Variance of a sum of independent random variables
Same as	Wikidata Q1148012 Wikipedia Coupon collector's problem

Markdown · JSON · Edit on GitHub

What this page needs for W1

an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.