Consider a sequence of independent trials, each of which is equally likely to result in any of the outcomes 0, 1, . . . ,m. Say that a round begins with the first trial, and that a new round begins each time outcome 0 occurs. Let N denote the number of trials that it takes until all of the outcomes 1, . . . ,m−1 have occurred in the same round.Also let $T_j$ denote the number of trials that it takes until j distinct outcomes have occurred and $I_j$ denote the jth distinct outcome to occur.(Therefore, outcome $I_j$ first occurs at trial $T_j$.
(a) I want to argue that random vectors $(I_1,...,I_m) and (T_1,...,T_m)$ are independent
(b)Define X by letting X=j if outcome j is the jth distict outcome to occur.(Thus $I_X=0$).Derive an equation for $E[N]$ in terms of $E[T_j]$, j = $1,...,m-1 by conditioning on X.
(c) Determine $E[T_j]$,j = 1,...,m-1.
(d)Find $E[N]$
Answer:
(a)By symmetry,for any value of $(T_1,...,T_m)$ the random vector $(I_1,...,I_j)$ is equally likely to be any of the m! permutations. Hence they are independent.
(b)$E[N] =\displaystyle\sum_{i=1}^m E[N|X=i]P(X) = i$
$E[N]=\frac1m\displaystyle\sum_{i=1}^mE[N|X=i]$
$E[N]=\frac1m\large(\displaystyle\sum_{i=1}^{m-1}(E[T_i]+E[N]) + E[T_{m-1}]\large)$
$E[N]=E[T_{m-1}] + \displaystyle\sum_{i=1}^{m-1} E[T_i]$
(c) $E[T_i] = \displaystyle\sum_{j=1}^{i}\frac{m}{m+1-j}$ because each $T_i$ is a geometric random variable with parameter $\frac{m+1-j}{m}$
(d)$E[N]=\displaystyle\sum_{j=1}^{m-1}\frac{m}{m+1-j}+\displaystyle\sum_{j=1}^{m-1}\displaystyle\sum_{j=1}^{i}\frac{m}{m+1-j}$
$E[N]=\displaystyle\sum_{j=1}^{m-1}\frac{m}{m+1-j}+\displaystyle\sum_{j=1}^{m-1}\displaystyle\sum_{i=j}^{m-1}\frac{m}{m+1-j}$
$E[N]=\displaystyle\sum_{j=1}^{m-1}\frac{m}{m+1-j}+\displaystyle\sum_{j=1}^{m-1}\frac{m(m-j)}{m+1-j}$
$E[N]=\displaystyle\sum_{j=1}^{m-1}\left(\frac{m}{m+1-j}+\frac{m(m-j)}{m+1-j}\right)$
$E[N]=m(m-1)$
