1
$\begingroup$

Possible Duplicate:
Expected time to roll all 1 through 6 on a die
A question about Poker (and probability in general)

Given a N-sided unbiased die. What is the expected number of throws of die so that each number is rolled at least once? Please anyone give a hint or solution to solve it.

1 Answers 1

0

There's a Wikipedia article about this problem: http://en.wikipedia.org/wiki/Coupon_collector%27s_problem

Suppose $k$ of the $N$ numbers have appeared so far. The probability that you get a new number on the next trial is then $(N-k)/N$. Let $X$ be the number of trials until that new number appears. Then $X$ is geoemtrically distributed on $\{1,2,3,\ldots\}$ and has expected value $N/(N-k)$ (e.g., if the probability of success on each trial is $1/15$ then the expected number of trials needed to get one success is $15$).

You're asking about the expected value of the sum of random variables like this one. The first has expected value $1$ (on the first trial, you necessarily get a new number). The second has expected value $N/(N-1)$. The third has expected value $N/(N-2)$. And so on. So the expected number of trials needed is

$ 1 + \frac{N}{N-1} + \frac{N}{N-2} + \frac{N}{N-3} + \cdots + \frac N3 + \frac N2 + \frac N1. $

  • 0
    @Didier: Sure, we can use that one instead -- as long as we don't keep producing more duplicates. I can't change my vote, but I presume if you and others vote to close as a duplicate of that one, that will be the one linked to in the end.2011-09-03