Expected number of trials for all possible outcomes to happen

combinatoricsprobabilityprobability distributions

Suppose that in each trial there are exactly $n$ possible outcomes with probabilities $p_1, \dots, p_n$ which sum to $1$.

I wonder what's the expected number of trials for all outcomes to happen at least once?

If there were only two outcomes then geometric distribution seems to solve the problem. But i don't see a simple way to generalize it for the current problem. Any ideas are highly appreciated.

Best Answer

Note that $$E(T)=\sum_{t=0}^\infty P(T>t)=\sum_{t=0}^\infty P(A(1,t)\cup A(2,t)\cup\cdots\cup A(n,t))$$ where, for each $k$, $A(k,t)$ denotes the event that none of the $t$ first tries produces the result $k$. Now, $$P(A(1,t)\cup A(2,t)\cup\cdots\cup A(n,t))=\sum_{i=1}^n(-1)^{i+1}\sum_{|I|=i}P(A(I,t))$$ where, for every $I\subseteq\{1,2,\ldots,n\}$, $$A(I,t)=\bigcap_{i\in I}A(i,t)$$ Thus, $$P(A(I,t))=(1-p_I)^t$$ where $$p_I=\sum_{i\in I}p_i$$ Collecting everything, one gets $$E(T)=\sum_{t=0}^\infty\sum_{i=1}^n(-1)^{i+1}\sum_{|I|=i}(1-p_I)^t$$ that is,

$$E(T)=\sum_{i=1}^n(-1)^{i+1}\sum_{|I|=i}\frac1{p_I}$$

This expresses $E(T)$ as the sum of $2^n-1$ terms. For example, for three different results, $$E(T)=\frac1{p_1}+\frac1{p_2}+\frac1{p_3}-\frac1{1-p_1}-\frac1{1-p_2}-\frac1{1-p_3}+1$$ In the equiprobable case, $p_k=1/n$ for every $k$ in $\{1,2,\ldots,n\}$, hence $$E(T)=\sum_{k=1}^n(-1)^{k+1}{n\choose k}\frac nk$$ Equivalently, $$E(T)=n\sum_{k=1}^n(-1)^{k+1}{n\choose k}\int_0^1x^{k-1}dx$$ that is, $$E(T)=n\int_0^1(1-(1-x)^n)\frac{dx}x=n\int_0^1\frac{1-x^n}{1-x}dx$$ or $$E(T)=n\int_0^1\sum_{i=0}^{n-1}x^idx$$ that is, finally, $$E(T)=n\sum_{i=1}^n\frac1i=nH_n$$ as already known.