Dice Problem

If you roll a single die 20 times, what is the probability you hit all six sides at least once?

Quote: Ace2

If you roll a single die 20 times, what is the probability you hit all six sides at least once?

Prob = 0.84799( monte carlo simulation)

I did some brute force computing, and I get 2,691,299,309,615 / 3,173,748,645,888 = 0.84798754, which is also about what I get through simulation.

Quote: ThatDonGuy

I did some brute force computing, and I get 2,691,299,309,615 / 3,173,748,645,888 = 0.84798754, which is also about what I get through simulation.

I agree. To hopefully get some solution credit, let me show you how I did it.

The left column shows the number of sides represented in the 20 rolls.

The second column from the left shows how many ways a specific such group can be arranged. For example, consider the probability that exactly 3 numbers are represented. There are combin(6,3)=20 such combinations of 3 out of 6 numbers.

The third column from the left shows the probability of each of such ways. This was the trickiest mathematically. In the case of all 6 numbers being represented, the formula is:

1 - 6*prob(exactly 5 numbers represented) + combin(6,4)*prob(exactly 4 numbers represented) - combin(6,3)*prob(exactly 3 numbers represented) + combin(6,2)*prob(exactly 2 numbers represented) - 6*prob(exactly 1 numbers represented).

In Excel, the formula can be written as 1 - sumproduct(column 2, column 3) below the current row.

The right column is the product of the second and third columns from the left.

Num sides rolled	Ways	Prob each	Probability
6	1	0.84798754088542100	0.84798754088542100
5	6	0.02458994388067370	0.14753966328404200
4	15	0.00029691568333819	0.00445373525007289
3	20	0.00000095281392563	0.00001905627851259
2	15	0.00000000028679665	0.00000000430194978
1	6	0.00000000000000027	0.00000000000000164
Total			1.00000000000000000

Here's how I did it:

Partition the numbers {1, 2, 3, ..., 20} into six non-empty partitions where the numbers in each partition are consecutive - for example, (1), (2...6), (7, 8), (9...16), (17), (18-20) represents one 1, five 2s, two 3s, eight 4s, one 5, and three 6s.
If P₁ through P₆ represent the number of dice in each partition, the number of permutations of the 20 dice that fall into this partition are 20! / (P₁! x P₂! x P₃! x P₄! x P₅! x P₆!).
Add all of these numbers up, and divide by 6²⁰.

I’ll bet Ace has a neat formula involving e and related to Poisson to get the answer.

@Unjon. Unfortunately I don’t think the Poisson integration method is applicable since it requires an infinite time space, and were dealing with 20 iterations here.

I suppose the easiest solution is via a Markov chain...there are only 6 states. That is how I initially solved it.

But closed-form solutions are generally preferable. Using inclusion exclusion we take the probability that an individual face has not been hit after 20 rolls, which is (5/6)^20, and multiply by 6. That gives us the “probability” that face 1 or 2 or 3 or 4 or 5 or 6 have not been hit, but it over-counts situations where more than one face hasn’t been hit. So we subtract (4/6)^20*15, which represents the chance that 2 of 6 faces haven’t appeared, times combin(6,2). Then add back (3/6)^20*20, which represents the chance that 3 of 6 faces haven’t appeared, times combin(6,3). Then subtract (2/6)^20*15, which represents the chance that 4 of 6 faces haven’t appeared, times combin(6,4). Finally add back (1/6)^20*6, which represents the chance that 5 of 6 faces haven’t appeared, times combin(6,5). This summation gives the probability that any side has not been hit, which is 0.152. The compliment is our answer of 0.848

The aforementioned summation can be simplified and written as:

(6^n - 6*5^n + 15*4^n - 20*3^n + 15*2^n - 6) / 6^n

Where n is the number of rolls.

For n=20 the formula yields 3100376804676480 / 3656158440062980 which reduces to 2691299309615 / 3173748645888 = 0.848

It looks the Wizard was on the right path to a formulaic solution.

100%, because they're all "due."

Quote: TigerWu

100%, because they're all "due."

I disagree. Any face has a 100% chance of hitting after 6 rolls, so all 6 will have a 100% chance of appearing after 36 rolls.

Quote: Ace2

I disagree. Any face has a 100% chance of hitting after 6 rolls, so all 6 will have a 100% chance of appearing after 36 rolls.

Ah! Of course... Silly me.