Vtyjkyuk

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.

Note that $$E(T)=sum_t=0^infty P(T>t)=sum_t=0^infty P(A(1,t)cup A(2,t)cupcdotscup 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)cupcdotscup A(n,t))=sum_i=1^n(-1)^i+1sum_=iP(A(I,t))$$ where, for every $Isubseteq1,2,ldots,n$, $$A(I,t)=bigcap_iin IA(i,t)$$ Thus, $$P(A(I,t))=(1-p_I)^t$$ where $$p_I=sum_iin Ip_i$$ Collecting everything, one gets $$E(T)=sum_t=0^inftysum_i=1^n(-1)^i+1sum_=i(1-p_I)^t$$ that is,

$$E(T)=sum_i=1^n(-1)^i+1sum_=ifrac1p_I$$

This expresses $E(T)$ as the sum of $2^n-1$ terms. For example, for three different results, $$E(T)=frac1p_1+frac1p_2+frac1p_3-frac11-p_1-frac11-p_2-frac11-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+1nchoose kfrac nk$$ Equivalently, $$E(T)=nsum_k=1^n(-1)^k+1nchoose kint_0^1x^k-1dx$$ that is, $$E(T)=nint_0^1(1-(1-x)^n)fracdxx=nint_0^1frac1-x^n1-xdx$$ or $$E(T)=nint_0^1sum_i=0^n-1x^idx$$ that is, finally, $$E(T)=nsum_i=1^nfrac1i=nH_n$$ as already known.