Section 3.3.2: Empirical Tests

Exercise 10. [M23] Solve exercise 8 for the more general coupon collector's test described in exercise 9.

Verified: yes
Solve time: 2m29s

---

Solution

Let $R$ denote the length of a single segment in the generalized coupon collector's test of exercise 9. The process stops when exactly $\delta$ distinct values have appeared, where $1 \le \delta \le d$.

Write

$$ R=X_1+X_2+\cdots+X_\delta, $$

where $X_j$ is the number of observations required to increase the number of distinct values from $j-1$ to $j$.

When $j-1$ distinct values have already been seen, there remain $d-(j-1)$ unseen values among the $d$ possible values. Hence

$$ P{\text{next observation is new}} =\frac{d-j+1}{d}. $$

Therefore $X_j$ has the geometric distribution

$$ P{X_j=m} =\left(\frac{j-1}{d}\right)^{m-1} \frac{d-j+1}{d}, \qquad m\ge1. $$

The waiting times $X_1,\ldots,X_\delta$ are independent, because after each new value is obtained the process starts afresh in a state determined only by the current number of distinct values.

For a geometric random variable with success probability $p$,

$$ E(X)=\frac1p, \qquad \operatorname{Var}(X)=\frac{1-p}{p^2}, $$

by equation 1.2.9-(28). Here

$$ p_j=\frac{d-j+1}{d}. $$

Hence

$$ E(X_j) =\frac{d}{d-j+1}, $$

and

$$ \operatorname{Var}(X_j)

\frac{1-p_j}{p_j^2}

\frac{(j-1)/d}{((d-j+1)/d)^2}

\frac{d(j-1)}{(d-j+1)^2}. $$

Since $R$ is the sum of independent variables,

$$ E(R)

\sum_{j=1}^{\delta}E(X_j)

d\sum_{j=1}^{\delta}\frac1{d-j+1}. $$

Setting $k=d-j+1$ gives

$$ E(R)

d\sum_{k=d-\delta+1}^{d}\frac1k. $$

Thus the average length of one generalized coupon collector segment is

$$ d\sum_{k=d-\delta+1}^{d}\frac1k. $$

If Algorithm C is continued until $n$ such segments have been found, the total number of observations is the sum of $n$ independent copies of $R$. Therefore

$$ E(T_n)

nd\sum_{k=d-\delta+1}^{d}\frac1k. $$

For the variance,

$$ \operatorname{Var}(R)

\sum_{j=1}^{\delta}\operatorname{Var}(X_j)

d\sum_{j=1}^{\delta} \frac{j-1}{(d-j+1)^2}. $$

Again substituting $k=d-j+1$,

$$ \operatorname{Var}(R)

d\sum_{k=d-\delta+1}^{d} \frac{d-k}{k^2}. $$

Hence

$$ \operatorname{Var}(T_n)

nd\sum_{k=d-\delta+1}^{d} \frac{d-k}{k^2}, $$

and the standard deviation is

$$ \sigma(T_n)

\sqrt{ nd\sum_{k=d-\delta+1}^{d} \frac{d-k}{k^2} }. $$

Therefore the generalized coupon collector test requires, on the average,

$$ \boxed{ nd\sum_{k=d-\delta+1}^{d}\frac1k } $$

observations before $n$ segments have been completed, and its standard deviation is

$$ \boxed{ \sqrt{ nd\sum_{k=d-\delta+1}^{d} \frac{d-k}{k^2} } }. $$

For $\delta=d$ these formulas reduce to the result of exercise 8:

$$ E(T_n)=nd\sum_{k=1}^{d}\frac1k, $$

and

$$ \sigma(T_n)

\sqrt{ nd\sum_{k=1}^{d} \frac{d-k}{k^2} }. $$

∎