Two Plus Two Publishing LLC
Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > >

Notices

Probability Discussions of probability theory

Reply
 
Thread Tools Display Modes
Old 06-21-2011, 10:39 PM   #1
Arouet
Carpal \'Tunnel
 
Arouet's Avatar
 
Join Date: Feb 2006
Posts: 6,433
Dice rolling question

Hi folks, on another forum we've been trying to figure out the proper way to calculate the average number of tries it would take to get the following:


We make a grid based on all the possibilities of two dice rolls: that is: 1/1, 1/2, 1/3 etc. for a total of 36 squares.

You then start rolling a die twice to match the squares, each time you get a hit on a square you scratch it off. (so you roll a 2 and a 3 you scratch off the 2/3 square). On average, how many rolls of the die would it take to hit every square once given a fair die.

Thanks in advance!
Arouet is offline   Reply With Quote
Old 06-21-2011, 11:16 PM   #2
spadebidder
Actually Shows Proof
 
spadebidder's Avatar
 
Join Date: Aug 2008
Location: This looks interesting.
Posts: 7,906
Re: Dice rolling question

I don't know the solution so I'd have to derive it. I might start with the fact that the chance in N trials to roll any specific one of N possibilities (where probability is 1/N) is given by
(e-1)/e = 63.2121% which is accurate for any large N and close for small N.

This implies that you will roll that percentage of all possibilities in 36 rolls.

We can also just use the binomial distribution in this case which gives us 63.729%. So in 36 rolls we expect to hit an average of only 23 of the available numbers.

Where to go from here?

If we roll another 36 times, we'll get an average of 23 numbers hit, and the chance of any one of them overlapping with the first set is (23/36)^2 = 40.8%, so we'd get on average (23 * (1 - .408)) = 14 more numbers. And 23 + 14 = 37. Hmmm. So it seems the answer is slightly under 72 rolls.

But I could be wrong, this is just an attempt to guess the solution.

Last edited by spadebidder; 06-21-2011 at 11:31 PM.
spadebidder is offline   Reply With Quote
Old 06-21-2011, 11:49 PM   #3
spadebidder
Actually Shows Proof
 
spadebidder's Avatar
 
Join Date: Aug 2008
Location: This looks interesting.
Posts: 7,906
Re: Dice rolling question

Approching the problem from another angle, what confidence level for hitting any specific value would this average number of rolls correspond to? For example, using the binomial we can say that to hit any specific number out of 36 with 99.9% confidence takes 250 rolls. But 50% confidence only takes 25 rolls. What number are we looking for? The 72 number I came up with before gives us about 87% confidence of hitting any specific number.
spadebidder is offline   Reply With Quote
Old 06-22-2011, 12:14 AM   #4
sallymustang
centurion
 
Join Date: Jun 2011
Posts: 123
Re: Dice rolling question

Quote:
Originally Posted by Arouet View Post
We make a grid based on all the possibilities of two dice rolls: that is: 1/1, 1/2, 1/3 etc. for a total of 36 squares.

You then start rolling a die twice to match the squares, each time you get a hit on a square you scratch it off. (so you roll a 2 and a 3 you scratch off the 2/3 square). On average, how many rolls of the die would it take to hit every square once given a fair die.

Thanks in advance!
My GFs and I just solved this for roulette (actually just verified an answer) and should be the same formula for craps for the 36 possible dice outcomes.

Being you are not using 2 dice my answer is for 2 dice but I guess you would just have to double it. I can not take credit for the formula. I found it over at the Wizard of Odds. HERE
My answer is 2*150.2841311

I hope this is right. see if this helps you.
In math class we ran simulations called 'wait for a complete set' to verify the formula and here is my summary.
Code:
trials:                  100,000   

minimum value:              55.00
first quartile:            119.00
median:                    143.00
third quartile:            173.00
maximum value:             536.00

mean value:                150.31

sample variance (n):      1940.31
sample variance (n-1):    1940.33
sample std dev (n):         44.05
sample std dev (n-1):       44.05
sallymustang is offline   Reply With Quote
Old 06-22-2011, 04:46 AM   #5
OmahaDonk
veteran
 
Join Date: Apr 2011
Posts: 2,778
Re: Dice rolling question

Quote:
Originally Posted by spadebidder View Post
Hmmm. So it seems the answer is slightly under 72 rolls.

But I could be wrong, this is just an attempt to guess the solution.
This seems too low, though I could be wrong.

my idea would be to define a variable X such that
E(X=i) is the expected value of rolls to scratch off i squares. We can define it recursively

E(X=1) = 1 (we always hit)
E(X=2) = E(X=1) + (1)(35/36) + (2)(1/36)(35/36) + (3)(1/36)^2(35/36) +..
E(X=3) = E(X=2) + (1)(34/36) + (2)(2/36)(34/36) + (3)(2/36)^2(34/36) +..

And we want E(X=36).

Too complicated for me
OmahaDonk is offline   Reply With Quote
Old 06-22-2011, 04:49 AM   #6
OmahaDonk
veteran
 
Join Date: Apr 2011
Posts: 2,778
Re: Dice rolling question

Quote:
Originally Posted by sallymustang View Post
My answer is 2*150.2841311
If all you say is right, then the answer should be the same as roulette (assuming you used 36 slots instead of 38) - just give each roll a roulette number. Or paste (1,3) over the roulette wheel for all 36 (x,y) combos . 150 sounds reasonable to me, too
OmahaDonk is offline   Reply With Quote
Old 06-22-2011, 07:02 AM   #7
Pyromantha
veteran
 
Join Date: Dec 2007
Posts: 2,228
Re: Dice rolling question

Expected length of time to scratch off all squares = 36/1 + 36/2 + 36/3 + 36/4 + ..... + 36/36

That is because the expected length of time to scratch them all off is the expected length of time before scratching the first square + expected length of time before scratching the second square + ..... + expected length of time before scratching off the last square.

When just the last square is uncovered, we have 1/36 chance of hitting it. So the time taken to hit it has a geometric distribution with parameter 1/36, which has an expectation of 36. See http://en.wikipedia.org/wiki/Geometric_distribution if unsure what a geometric distribution is.

With two squares left we have 2/36 chance of hitting one of them. So the time to hit one of them is geometric with parameter 2/36, with expectation 36/2. Etc.

That sum gives 150.28.

This type of problem is a 'coupon collectors problem'. See http://en.wikipedia.org/wiki/Coupon_...or%27s_problem

A trickier question is what is the number of throws needed if (1,2) and (2,1) are the same roll (so 21 total squares)? You could do this with generating functions, I usually make a mess of complicated math so will leave this to better minds.

Last edited by Pyromantha; 06-22-2011 at 07:20 AM.
Pyromantha is offline   Reply With Quote
Old 06-22-2011, 07:37 AM   #8
BruceZ
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,877
Re: Dice rolling question

Quote:
Originally Posted by sallymustang View Post
My GFs and I just solved this for roulette (actually just verified an answer) and should be the same formula for craps for the 36 possible dice outcomes.

Being you are not using 2 dice my answer is for 2 dice but I guess you would just have to double it. I can not take credit for the formula. I found it over at the Wizard of Odds. HERE
My answer is 2*150.2841311
No need to double that. 150.2841311 is correct.

The value for the median, or other probabilities, can be obtained by inclusion-exclusion.
BruceZ is offline   Reply With Quote
Old 06-22-2011, 08:29 AM   #9
spadebidder
Actually Shows Proof
 
spadebidder's Avatar
 
Join Date: Aug 2008
Location: This looks interesting.
Posts: 7,906
Re: Dice rolling question

Ah yes, the coupon collecting problem. I'll remember this problem type next time.
spadebidder is offline   Reply With Quote
Old 06-22-2011, 09:35 AM   #10
Arouet
Carpal \'Tunnel
 
Arouet's Avatar
 
Join Date: Feb 2006
Posts: 6,433
Re: Dice rolling question

You guys are awesome! Very helpful! Thanks so much!

@pyro; no 2,1 and 1,2 are treated as different.
Arouet is offline   Reply With Quote
Old 06-22-2011, 09:49 AM   #11
Pyromantha
veteran
 
Join Date: Dec 2007
Posts: 2,228
Re: Dice rolling question

Quote:
Originally Posted by Arouet View Post
You guys are awesome! Very helpful! Thanks so much!

@pyro; no 2,1 and 1,2 are treated as different.
Yep, but the question is *much* more interesting mathematically if they are treated the same, so that some squares have different probabilities.

A related interesting question is what is the expected number of throws of two dice, until you have collected all possible totals from 2,3,....., 12. Anyone fancy having a go at that?
Pyromantha is offline   Reply With Quote
Old 06-22-2011, 10:42 AM   #12
hepzebah
adept
 
Join Date: Aug 2008
Posts: 714
Re: Dice rolling question

Quote:
Originally Posted by Pyromantha View Post
A related interesting question is what is the expected number of throws of two dice, until you have collected all possible totals from 2,3,....., 12. Anyone fancy having a go at that?
Depends on whether I've made my point or not.
hepzebah is offline   Reply With Quote
Old 06-22-2011, 03:23 PM   #13
RollWave
Carpal \'Tunnel
 
RollWave's Avatar
 
Join Date: Nov 2007
Location: PL Daily Action Thread
Posts: 12,494
Re: Dice rolling question

Quote:
Originally Posted by Pyromantha View Post
Yep, but the question is *much* more interesting mathematically if they are treated the same, so that some squares have different probabilities.

A related interesting question is what is the expected number of throws of two dice, until you have collected all possible totals from 2,3,....., 12. Anyone fancy having a go at that?
wizard of odds gives the odds of the "All" bet as 1 in 190.2.

This bet is hitting 2-6 and 8-12 all before hitting a 7. Not the same problem, but on the track.
RollWave is offline   Reply With Quote
Old 06-23-2011, 05:30 AM   #14
R Gibert
adept
 
Join Date: Jan 2006
Posts: 936
Re: Dice rolling question

Quote:
Originally Posted by Pyromantha View Post
Yep, but the question is *much* more interesting mathematically if they are treated the same, so that some squares have different probabilities.

A related interesting question is what is the expected number of throws of two dice, until you have collected all possible totals from 2,3,....., 12. Anyone fancy having a go at that?
I wrote a short Monte Carlo program and ran it 1,000,000 times. The expected number of throws came out to about 61.2
R Gibert is offline   Reply With Quote
Old 06-23-2011, 04:41 PM   #15
OmahaDonk
veteran
 
Join Date: Apr 2011
Posts: 2,778
Re: Dice rolling question

Quote:
Originally Posted by Pyromantha View Post

A related interesting question is what is the expected number of throws of two dice, until you have collected all possible totals from 2,3,....., 12. Anyone fancy having a go at that?
I asked my father, who is somewhat of a math guru - with no explanation he says he believes its 54. Thanks dad.
OmahaDonk is offline   Reply With Quote
Old 06-23-2011, 07:49 PM   #16
sallymustang
centurion
 
Join Date: Jun 2011
Posts: 123
Re: Dice rolling question

Quote:
Originally Posted by R Gibert View Post
I wrote a short Monte Carlo program and ran it 1,000,000 times. The expected number of throws came out to about 61.2
Me too. The math is way to hard.
Maybe not for some members here.

As for a practical application - In my short gambling life I have seen 2 roulette players bet for a complete set and they both won before going bankrupt.
I guess if one played Crapless Craps they could possibly use this knowledge to bet on the 11 numbers. Maybe...
Code:
trials:                  1,000,000   

minimum value:               11.00
first quartile:              36.00
median:                      52.00
third quartile:              76.00
maximum value:              512.00

mean value:                  61.23

sample variance (n):       1297.51
sample std dev (n):          36.02
How about the 21 unique combinations.
These can be bet on at some Craps tables that offer all the hop bets. Well, with very high house edges, maybe not
Code:
mean	94.96
median	86
mode	72
min	27
max	528
sd	39.01
sallymustang is offline   Reply With Quote
Old 06-24-2011, 10:18 AM   #17
BruceZ
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,877
Re: Dice rolling question

Quote:
Originally Posted by OmahaDonk View Post
I asked my father, who is somewhat of a math guru - with no explanation he says he believes its 54. Thanks dad.
54 is just the average number of rolls to get the 2 rarest numbers 2 and 12. That is 18 + 36. Clearly the average number to get all of them is greater than this, otherwise we would have to be guaranteed to always get the others first.
BruceZ is offline   Reply With Quote
Old 06-24-2011, 10:10 PM   #18
OmahaDonk
veteran
 
Join Date: Apr 2011
Posts: 2,778
Re: Dice rolling question

Quote:
Originally Posted by BruceZ View Post
54 is just the average number of rolls to get the 2 rarest numbers 2 and 12. That is 18 + 36. Clearly the average number to get all of them is greater than this, otherwise we would have to be guaranteed to always get the others first.
Yeah, when I pressed him for some sort of analysis, he said that's what he thought I wanted. Will see if he does the more difficult problem
OmahaDonk is offline   Reply With Quote
Old 06-26-2011, 05:14 AM   #19
BruceZ
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,877
Re: Dice rolling question

Quote:
Originally Posted by OmahaDonk View Post
Yeah, when I pressed him for some sort of analysis, he said that's what he thought I wanted. Will see if he does the more difficult problem
I got it *trumpets*.

I figured out how to compute the average number of rolls to get all of the numbers 2-12. The answer is 61.21738 rolls. The principle is simple, but the computations were automated to get the exact result.

The average rolls to get a 2 is 36. The average rolls to get a 2 and a 12 is

36 + (1-0.5)*36 = 54

The 0.5 is there because half of the time the 12 will come before the 2, and so the other half of the time it comes after the 2, in which case we need another 36 rolls to get the 12.

To understand the remaining terms, refer to this table, where E is the average number of rolls for each number.

Code:
number     prob (in 36)     E

2                1          36
12               1          36
3                2          18
11               2          18
4                3          12
10               3          12
5                4           9
9                4           9
6                5           7.2
8                5           7.2
7                6           6
Now to include another number, say 3, we get

54 + [1 - (2/3 + 2/3 - 2/4)]*18 = 57

The value in () is the probability that the 3 will come before either the 2 or the 12 by inclusion-exclusion. The probability is 2/3 that it comes before the 2, plus 2/3 that it comes before the 12, minus 2/4 that it comes before both. 1 minus that fraction of the time it comes after both, in which case we need another 18 rolls to get the 3 since it has probability 1/18.

The next one for including the 11 is

57 + [1 - (2/3 + 2/3 + 2/4 - 2/4 -2/5 - 2/5 + 2/6)]*18 = 59.4

The value in () is the probability that the 11 will come before the 2, 12, or 3. In this case, we add the 3 probabilities for coming before each of the previous 3 numbers, then subtract the 3 probabilites for coming before each of the C(3,2) = 3 combinations of 2 of the 3 numbers, then add back the probability of coming before all 3 numbers. 1 minus this fraction of the time it comes after all 3, in which case we need another 18 rolls to get the 11 since it has probability 1/18.

The next term for including the 4 is

59.4 + [1 - (3/4 + 3/4 + 3/5 + 3/5 - 3/5 - 3/6 - 3/6 - 3/6 -3/6 -3/7 + 3/7 + 3/7 + 3/8 + 3/8 - 3/9)]*12

=~ 60.05714

The value in () is the probability that the 4 will come before the 2, 12, or 3, or 11. In this case, we add the 4 probabilities for coming before each of the previous 4 numbers, then subtract the 6 probabilites for coming before each of the C(4,2) = 6 combinations of 2 of the 4 numbers, then add back the 4 probabilities of coming before each of the C(4,3) = 4 numbers, then subtract the probability of coming before all 4 numbers. 1 minus this fraction of the time it comes after all 4, in which case we need another 12 rolls to get the 4 since it has probability 1/12.

As you can see, the calculations are getting complicated quickly, and we still have 6 numbers to go. However, the numbers in [] are guaranteed to keep getting smaller since the probability of each number being after all the previous numbers gets smaller as we have more numbers and as the numbers become more probable. At this point, we know that the remaining rolls to be added must be smaller than than the last term in [], which is about 0.054762, times the sum of the average number of rolls for the remaining numbers. So the final answer T must be

T > 60.0571

and

T < 60.05741 + 0.054762*(12+9+9+7.2+7.2+6) =~ 62.81741

So by hand we have computed that it must lie between these two numbers.

Now these terms follow a pattern which I've identified, and such a pattern could be used either in an automated program to compute all of the terms, or it could possibly be used to find a generating function. However, R provides us with a convenient function which will enumerate the combinations of the elements in an array slice. This is exactly what we need here, and this makes the R program to compute all the terms very short. The function is called combn. It returns a 2-dimensional array with the combinations of a given size in each column. We sum these columns for each size combination just as we have been doing by hand.

The following R program computes the exact answer, which comes to 61.21738 rolls, in agreement with the simulations.

Code:
in_36 = c(1,1,2,2,3,3,4,4,5,5,6)
E = c(36,36,18,18,12,12,9,9,7.2,7.2,6)
T = 36
for (i in 2:11) {
  p = 0
  for (j in 1:(i-1)) {
    terms = combn(in_36[1:(i-1)],j)
    for (k in 1:(length(terms)/j)) {
      p = p + (-1)^(j+1) * in_36[i]/(in_36[i] + sum(terms[1:j,k]))
    }
  }
  T = T + (1-p)*E[i]
}

T

Last edited by BruceZ; 06-27-2011 at 07:34 PM. Reason: typo, few more words of explanation
BruceZ is offline   Reply With Quote
Old 06-26-2011, 06:18 AM   #20
guardiola
newbie
 
Join Date: May 2011
Posts: 24
Re: Dice rolling question

Very clever how BruceZ obtained the answer 61.217 for the two-dice problem with outcomes 2,...,12. Using a tricky approach, Sheldon Ross obtained in his book Introduction to Probability Models the answer to the general coupon collector's problem. Suppose you have $n$ possible outcomes with respective probabilities $p_1,..., p_n$ , then the expected number of trials until you have obtained all possible outcomes is given by the intimidating formula

$E(T)=\inf{0}^{\infty}[1-(1-exp(-p_1 t))*...*-(1-exp(-p_n t))]dt.

In this way you also obtain the answer $E(T)=61.217$ for the two-dice problem with outcomes 2,..,12. However, this requires heavy artillery. How much simpler is the approach of BruceZ.

Note: the integral can numerically be computed by using the free tool www.wolframalpha.com

Last edited by guardiola; 06-26-2011 at 06:32 AM. Reason: hint
guardiola is offline   Reply With Quote
Old 02-23-2012, 03:31 PM   #21
BruceZ
Carpal \'Tunnel
 
BruceZ's Avatar
 
Join Date: Sep 2002
Posts: 11,877
Re: Dice rolling question

I'm bumping this to keep it out of the archive because the Wizard of Odds did a column about my solution and linked to it. He did that back in November, and I just found out about it now. That was for the average rolls to get all the numbers 2-12.

http://wizardofodds.com/ask-the-wizard/278/

4th answer down.

Last edited by BruceZ; 02-23-2012 at 03:47 PM.
BruceZ is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off


Forum Jump


All times are GMT -4. The time now is 06:50 PM.


Powered by vBulletin®
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
Copyright 2008-2020, Two Plus Two Interactive
 
 
Poker Players - Streaming Live Online