Problem 11.1 Easy Free 4 variations

Coupon Collector

A standard fair six-sided die is rolled repeatedly. Find the expected number of rolls needed for every face to have appeared at least once.

Work it out, then compare with the answer.

SolutionShow the worked solution

Let $T$ be the number of rolls and split it into stages: $T=T_1+\dots+T_6$ , where $T_i$ is the number of rolls taken to see the $i$ th distinct face once $i-1$ faces have appeared.

While $i-1$ faces have been seen, each roll shows a new face with probability $\frac{7-i}{6}$ , independently of earlier rolls. So $T_i\sim\mathrm{Geom}\!\left(\frac{7-i}{6}\right)$ and $\mathbb{E}[T_i]=\frac{6}{7-i}$ . In particular $T_1=1$ .

By linearity of expectation,

\mathbb{E}[T]=\sum_{i=1}^{6}\frac{6}{7-i}=6\sum_{j=1}^{6}\frac1j=6\cdot\frac{49}{20}=\frac{147}{10}.

\boxed{\mathbb{E}[T]=6H_6=\tfrac{147}{10}=14.7}

Generalisation. For $n$ equally likely types the same argument gives $\mathbb{E}[T]=nH_n=n\sum_{j=1}^n\frac1j\approx n\ln n$ .

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 11.1a

A collector draws stamps one at a time, each independently and uniformly one of four types. Find the expected number of stamps she must draw until she has collected three distinct types (not necessarily all four).

Work it out, then compare with the answer.

Solution

Keep only the first three stages of the four-type collector. With $k$ types already held, a draw is new with probability $\frac{4-k}{4}$ . The expected number of draws is therefore

1+\frac43+\frac42=\frac{13}{3}\approx 4.33.

\boxed{\tfrac{13}{3}}

Variation 11.1b

A farmer examines goats one at a time; each goat is independently male with probability $3/4$ and female with probability $1/4$ . He stops as soon as he has examined a male and a female (in either order). Letting $N$ be the number of goats examined when he stops, find $\mathbb{E}[N]$ .

Work it out, then compare with the answer.

Solution

Condition on the first goat.

If it is male (probability $\frac34$ ), the farmer then waits a $\mathrm{Geom}(\frac14)$ number of goats for a female, so $\mathbb{E}[N\mid M]=1+4=5$ .
If it is female (probability $\frac14$ ), he waits a $\mathrm{Geom}(\frac34)$ number for a male, so $\mathbb{E}[N\mid F]=1+\frac43=\frac73$ .

Hence

\mathbb{E}[N]=\tfrac34\cdot 5+\tfrac14\cdot\tfrac73=\tfrac{45}{12}+\tfrac{7}{12}=\tfrac{13}{3}.

\boxed{\mathbb{E}[N]=\tfrac{13}{3}}

Variation 11.1c

Consider the complete directed graph on $11$ nodes (no self-loops): from any node, each of the other $10$ nodes is reached with probability $1/10$ on each step. Starting from one node and taking such steps repeatedly, find the expected number of steps needed to have visited every node at least once, rounded to the nearest integer.

Work it out, then compare with the answer.

Solution

The starting node counts as visited at step $0$ .

When $k$ nodes have been visited, the walker stands on one of them. Its next step goes to one of the $11-k$ unvisited nodes with probability $\frac{11-k}{10}$ , since self-loops are excluded. The wait for the next new node is therefore $\mathrm{Geom}\!\left(\frac{11-k}{10}\right)$ .

Summing the means over $k=1,\dots,10$ ,

\sum_{k=1}^{10}\frac{10}{11-k}=10H_{10}=\frac{7381}{252}\approx 29.29.

\boxed{10H_{10}=\tfrac{7381}{252}\approx 29}

If one also counted the initial placement as a step, the total would be $1+10H_{10}\approx 30$ .

Variation 11.1d

An ant starts at a vertex of a regular $n$ -simplex (so there are $n+1$ vertices in total). At each step it jumps to one of the other $n$ vertices, chosen uniformly at random (no self-loops). The ant stops the first time it has visited every vertex at least once and returned to its starting vertex. Find the expected number of steps, as a function of $n$ .

Work it out, then compare with the answer.

Solution

Covering stage. The start vertex is visited at time $0$ . With $k$ vertices visited ( $1\le k\le n$ ), a jump lands on a new vertex with probability $\frac{n+1-k}{n}$ . Visiting all $n+1$ vertices therefore takes expected time

\sum_{k=1}^{n}\frac{n}{n+1-k}=nH_n.

Return stage. At the moment the last vertex is first reached, the ant is not at the start, because the start was visited at time $0$ . From any non-start vertex it jumps to the start with probability $\frac1n$ . The return time is thus $\mathrm{Geom}(\frac1n)$ , with mean $n$ .

Adding the two stages,

\boxed{\,nH_n+n=n\left(1+\sum_{j=1}^n\frac1j\right)\,}

Check. For $n=1$ the formula gives $2$ , which is correct: one step out and one step back.

Spotted an error? Email us