Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 19
  • Posts: 560
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
ssho88
ssho88
Joined: Oct 16, 2011
  • Threads: 41
  • Posts: 427
March 25th, 2020 at 7:19:42 PM permalink
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)
Last edited by: ssho88 on Mar 25, 2020
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 92
  • Posts: 4101
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.
Wizard
Administrator
Wizard
Joined: Oct 14, 2009
  • Threads: 1317
  • Posts: 21598
March 26th, 2020 at 4:02:55 AM permalink
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
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.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 92
  • Posts: 4101
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 P1 through P6 represent the number of dice in each partition, the number of permutations of the 20 dice that fall into this partition are 20! / (P1! x P2! x P3! x P4! x P5! x P6!).
Add all of these numbers up, and divide by 620.
unJon
unJon
Joined: Jul 1, 2018
  • Threads: 13
  • Posts: 1689
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.
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 19
  • Posts: 560
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.
Last edited by: Ace2 on Mar 26, 2020
Itís all about making that GTA
TigerWu
TigerWu
Joined: May 23, 2016
  • Threads: 21
  • Posts: 4022
March 26th, 2020 at 9:06:50 AM permalink
100%, because they're all "due."
Ace2
Ace2
Joined: Oct 2, 2017
  • Threads: 19
  • Posts: 560
March 26th, 2020 at 9:10:28 AM permalink
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.
Itís all about making that GTA
TigerWu
TigerWu
Joined: May 23, 2016
  • Threads: 21
  • Posts: 4022
March 26th, 2020 at 9:20:51 AM permalink
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.

  • Jump to: