Section 3.3.2: Empirical Tests

Exercise 9. [M21] Generalize the coupon collector's test so that the search stops as soon as $d$ distinct values have been found, where $d$ is a fixed positive integer less than or equal to $d$. What probabilities should be used in place of (6)?

Verified: yes
Solve time: 2m09s

---

Solution

Let $L$ denote the length of one coupon-collector segment produced by Algorithm C. The algorithm examines successive values until each of the $d$ possible values $0,1,\ldots,d-1$ has appeared at least once. Thus $L$ is the classical coupon-collector waiting time.

Write

$$ L=X_1+X_2+\cdots+X_d, $$

where $X_k$ is the number of observations required to increase the number of distinct values already seen from $k-1$ to $k$.

Suppose $k-1$ distinct values have already appeared. Then $d-(k-1)$ values have not yet appeared. Each new observation produces a previously unseen value with probability

$$ p_k=\frac{d-k+1}{d}. $$

Therefore $X_k$ has the geometric distribution

$$ P{X_k=m}=(1-p_k)^{m-1}p_k, \qquad m\ge1, $$

and the random variables $X_1,\ldots,X_d$ are independent.

For a geometric random variable with parameter $p$,

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

by Eq. 1.2.9-(28). Hence

$$ E(X_k)=\frac{d}{d-k+1}, $$

and

$$ \operatorname{Var}(X_k)

\frac{1-\frac{d-k+1}{d}} {\left(\frac{d-k+1}{d}\right)^2}

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

The expected length of one segment is therefore

$$ E(L)

\sum_{k=1}^{d} E(X_k)

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

If

$$ H_d=\sum_{k=1}^{d}\frac1k $$

denotes the $d$th harmonic number,

$$ E(L)=dH_d. $$

Algorithm C finds $n$ complete sets in succession. Let

$$ T_n=L_1+\cdots+L_n, $$

where $L_1,\ldots,L_n$ are the lengths of the $n$ segments. Since the segments are formed from disjoint portions of an independent random sequence, the $L_i$ are independent and identically distributed. Hence

$$ E(T_n)

nE(L)

ndH_d. $$

Thus the average number of $U$'s required before $n$ complete sets have been found is

$$ \boxed{ndH_d}. $$

To compute the variance,

$$ \operatorname{Var}(L)

\sum_{k=1}^{d}\operatorname{Var}(X_k)

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

Let $j=d-k+1$. Then

$$ \operatorname{Var}(L)

d\sum_{j=1}^{d}\frac{d-j}{j^2}

d\left( d\sum_{j=1}^{d}\frac1{j^2}

\sum_{j=1}^{d}\frac1j \right). $$

Therefore

$$ \operatorname{Var}(T_n)

n,\operatorname{Var}(L)

nd\left( d\sum_{j=1}^{d}\frac1{j^2}

\sum_{j=1}^{d}\frac1j \right). $$

The standard deviation is

$$ \boxed{ \sqrt{ nd\left( d\sum_{j=1}^{d}\frac1{j^2}

\sum_{j=1}^{d}\frac1j \right) } }. $$

Equivalently, in terms of the harmonic numbers

$$ H_d=\sum_{j=1}^{d}\frac1j, \qquad H_d^{(2)}=\sum_{j=1}^{d}\frac1{j^2}, $$

the answers are

$$ \boxed{E(T_n)=ndH_d}, $$

and

$$ \boxed{\sigma(T_n)=\sqrt{nd\bigl(dH_d^{(2)}-H_d\bigr)}}. $$