March 25th, 2020 at 5:57:28 PM
permalink

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

It’s all about making that GTA

March 25th, 2020 at 7:19:42 PM
permalink

Quote:Ace2If 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)

Last edited by: ssho88 on Mar 25, 2020

March 25th, 2020 at 9:46:20 PM
permalink

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.

March 26th, 2020 at 4:02:55 AM
permalink

Quote:ThatDonGuyI 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 |

Last edited by: Wizard on May 21, 2020

It's not whether you win or lose; it's whether or not you had a good bet.

March 26th, 2020 at 6:33:31 AM
permalink

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

Add all of these numbers up, and divide by 6

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

_{1}through P_{6}represent the number of dice in each partition, the number of permutations of the 20 dice that fall into this partition are 20! / (P_{1}! x P_{2}! x P_{3}! x P_{4}! x P_{5}! x P_{6}!).Add all of these numbers up, and divide by 6

^{20}.
March 26th, 2020 at 8:01:54 AM
permalink

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

The race is not always to the swift, nor the battle to the strong; but that is the way to bet.

March 26th, 2020 at 8:47:18 AM
permalink

@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.

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.

Last edited by: Ace2 on Mar 26, 2020

It’s all about making that GTA

March 26th, 2020 at 9:06:50 AM
permalink

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

March 26th, 2020 at 9:10:28 AM
permalink

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:TigerWu100%, because they're all "due."

It’s all about making that GTA