Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
This is a variant on the coupon collectors problem. The answer should be available through a net search, and should be close to 1/s, where s is the smallest among the probability values p_i. Gerhard "Ask Me About System Design" Paseman, 2011.04.14 –  Gerhard Paseman Apr 14 '11 at 7:54
1  
In the symmetric case the answer is closer to $-\log(s)/s$. –  Did Apr 14 '11 at 8:28
    
Could you please clarify what type of answer you want, and whether there are particular $d$-tuples of interest? @Gerhard That $1/s$ estimate is interesting since it fails for the classic problem, but should be approximately right when the other probabilities are much larger. Can you say how much larger they need to be? –  Douglas Zare Apr 14 '11 at 8:31
    
Based on Didier,s answer, I would guess that 1/s need not be much larger than ne, with n the number of sides. This is physical intuition however; I haven't taken time out to research or simulate it, and presently I have no conscious memory of having seen the problem before. Gerhard "Ask Me About System Design" Paseman, 2011.04.14 –  Gerhard Paseman Apr 14 '11 at 17:25
add comment

2 Answers

up vote 5 down vote accepted

For the symmetric case when $p_i=1/d$ for every $i$, see here. 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.)

share|improve this answer
    
Thanks for the nice answer Didier. –  user14324 Apr 14 '11 at 12:40
    
For what it's worth, this result goes back to: von Schelling, H., (1934). Auf der Spur des Zufalls. Deutsches Statistisches Zentralblatt, 26, 137-146. An English translation appeared later (in a much more accessible location): von Schelling, H., (1954). Coupon Collecting for Unequal Probabilities, Amer. Math. Monthly, 61, no. 5, 306-311. –  Russell May Dec 8 '11 at 13:17
add comment

You may also find the answers of this Math SE question helpful.

The average number of unique observations $E(M)$ is given in Henry's answer here, at least in the case of a fair die.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.