Thread Rating:

Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
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
  • Threads: 53
  • Posts: 657
Joined: Oct 16, 2011
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
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
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
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
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
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
ThatDonGuy
ThatDonGuy
  • Threads: 117
  • Posts: 6219
Joined: Jun 22, 2011
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
  • Threads: 14
  • Posts: 4574
Joined: Jul 1, 2018
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
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
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
  • Threads: 25
  • Posts: 5509
Joined: May 23, 2016
March 26th, 2020 at 9:06:50 AM permalink
100%, because they're all "due."
Ace2
Ace2
  • Threads: 32
  • Posts: 2672
Joined: Oct 2, 2017
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
  • Threads: 25
  • Posts: 5509
Joined: May 23, 2016
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: