Let's say that I have a loaded $d$-sided die where the relative probabilities for the die landing on a particular side, $(p\_1, ..., p\_d)$, are known. How many times must I roll the die to, on average, to sample all possible outcomes at least once?


I hope this isn't too low level a question...


Edit: Didier just nicely answered my original question, but maybe folks here will tolerate one further follow-up: Let's say that I roll the die $k$ times, where $k$ is less than the expected average number of rolls necessary to sample all states of the die. What is the average number of unique states I've sampled as a function of $k$ rolls?



Number of required trials to sample all possible states of a 'd'-sided loaded die
For the symmetric case when $p\_i=1/d$ for every $i$, see [here](https://math.stackexchange.com/questions/28905). The answer is
$$
E(T)=\sum\_{k=1}^d\frac{d}{k},
$$
where $T$ is the number of times the die has been rolled at the first instant when all the possible outcomes have been sampled at least once. 


In the general case, the event $[T\ge n+1]$ means that at least one outcome has not been sampled yet, hence $[T\ge n+1]$ is the union over $k$ of the events $A\_n(k)$ where $A\_n(k)=[$The outcome $k$ has not been sampled during the first $n$ rolls$]$. 


For every subset $I$ of $\{1,2,\ldots,d\}$, let $A\_n(I)$ denote the intersection of the events $A\_n(k)$ for $k$ in $I$. By inclusion-exclusion $P(T\ge n+1)$ is the sum of $(-1)^{|I|-1}P(A\_n(I))$ over every non empty subset $I$ of $\{1,2,\ldots,d\}$. 


For every $I$, $A\_n(I)$ means that the $n$ first outcomes have been chosen in the complement of $I$, hence $P(A\_n(I))=(1-p(I))^n$ where $p(I)$ is the sum of $p\_k$ over $k$ in $I$. Hence,
$$
E(T)=\sum\_{n\ge0}P(T\ge n+1)=\sum\_{I\ne\emptyset}(-1)^{|I|-1}\sum\_{n\ge0}(1-p(I))^n=\sum\_{I\ne\emptyset}(-1)^{|I|-1}\frac1{p(I)}.
$$
This can be rewritten as
$$
E(T)=\sum\_k\frac1{p\_k}-\sum\_{k\_1\ne k\_2}\frac1{p\_{k\_1}+p\_{k\_2}}+\sum\_{k\_i\ne k\_j}\frac1{p\_{k\_1}+p\_{k\_2}+p\_{k\_3}}+\cdots+(-1)^{d-1}.
$$
It is an interesting exercise to recover the formula of the symmetric case from this one. (Hint: generating functions.)


