5
$\begingroup$

Dice odds seem simple at first glance, but I've never taken a Calculus based statistics course or game theory, and I think I may need to in order to solve some of the things I'm trying to solve. I can hammer out the odds in some of the more straight-forward scenarios, but when it comes to calculating the odds of a series of dice events with variable conditions... I get lost in the numbers. I've tried different, seemingly legit methods... only to return vastly different figures each time. Casino craps tables have a great variety of bets and hedge bets you can make. Some of the bets you make can sit on the table for half an hour or more, through dozens and dozens of dice throws, waiting on a resolution. It's technically possible (in theory not fact) that some of these bets could go on forever without being resolved. I would really like a decent approach to calculating these odds myself... hopefully by presenting a particular scenario, I can pick up enough tid-bits from your answers to piece together the methodology:

  1. We're throwing two six-sided dice at a time.
  2. Each side of each dice has equal probability on any given throw.
  3. There exists a tracking list with the numbers: 2, 3, 4, 5, 6, 8, 9, 10, 11, 12. (Note: 7 is not in this list.)
  4. When the dice are thrown and their total is a number other than 7, the number is crossed off the tracking list and the dice are rolled again.
  5. When the dice are thrown and their total is a number that's already been crossed off the tracking list, the dice are rolled again.
  6. At any point if the dice are thrown and their total is 7, the series is resolved as a loss.
  7. At any point if all ten numbers are crossed off the tracking list, the series is resolved as a win.

What's the probability of crossing all ten numbers off the list (winning) before throwing a 7 (losing)?

This is the"All or Nothing at All" bonus bet newly popular at many casinos. It pays 175 to 1. There are also "All Small" and "All Tall" bonus bets that pay 34 to 1 for throwing 2 thru 6 or 8 thru 12 respectively before throwing the 7. There's also a "Fire Bet" I'd like to break apart, but the rules are quite different. It will require a new post if I can't cull some new insights from the answers here... Please bear in mind, I'm wanting to know how to calculate conditional dice probability (where instantaneous probability shifts depending on your progression from throw to throw), not just know the odds in this particular case. I've taken mathematics courses up through CalcIII, so I can understand discussions involving limits and summation. Again, I've never takes statistics, probability, or game theory. Sorry for the long post, I know I talk too much....

$\endgroup$
1
  • $\begingroup$ I mentioned my comprehension level in my question and said, "Please bear in mind I want to know how to calculate... not just know the odds in this particular case." You guys have done some brilliant looking work in your answers, but I understood little of it other than the bare answer. I wasn't trying to open a competition to see who was the smartest, I wanted to learn. I've never used matrices for anything other than solving n-equations with n-unknowns. My vectors point direction in xyz coordinate systems. I "program" using spreadsheets, not compilers. You guys kind of missed the point... $\endgroup$ – reubix_part3 Jun 5 '15 at 4:35
2
$\begingroup$

Seems like a version of the (difficult) coupon collector problem with unequal probabilities. You might want to simulate it. Here are some exact results on simplified versions of the problem:

1) Suppose all 11 choices $\{2, \ldots, 12\}$ have equal probability. The probability of getting all non-7 numbers before seeing "7" is then the probability that 7 is the last number to be seen. Since all 11 numbers have an equal chance of being the "last to be seen," this probability is $1/11$. It can also be calculated as: $$ \left(\frac{10}{11}\right)\left(\frac{9}{10}\right)\left(\frac{8}{9}\right)\cdots \left(\frac{1}{2}\right) = \frac{1}{11} $$

2) Suppose the chance of getting $7$ is $1/6$ (which it really is), but pretend all 10 other numbers have equal probability of $(5/6)\frac{1}{10}$. The probability of getting 7 last is: $$ \left(\frac{5}{6}\right)\left(\frac{(5/6)(9/10)}{1/6+(5/6)(9/10)}\right)\left(\frac{(5/6)(8/10)}{1/6+(5/6)(8/10)}\right)\left(\frac{(5/6)(7/10)}{1/6+(5/6)(7/10)}\right)\cdots\left(\frac{(5/6)(1/10)}{1/6+(5/6)(1/10)}\right) $$ This simplifies to: $$ \left(\frac{5}{6}\right)\left(\frac{1}{\frac{2}{9}+1}\right)\left(\frac{1}{\frac{2}{8}+1}\right)\left(\frac{1}{\frac{2}{7}+1}\right)\cdots\left(\frac{1}{\frac{2}{1}+1}\right) = \frac{1}{66} $$

3) The true answer: The true answer would be less than $1/66$ since pretending all 10 other numbers have equal probabilities of $(5/6)(1/10)$ makes it more likely to see everything else before seeing 7.


As another variation, you can exactly compute the expected number of distinct numbers rolled before seeing "7." The answer is $\approx 3.161472$, whereas winning the game requires you to see all 10 before seeing "7." Here is the computation:

Define $X$ as the amount of distinct numbers seen before seeing "7." So $X \in \{0, 1, 2, \ldots, 10\}$. Imagine an infinite sequence of dice rolls. For each $i \in \{1, 2, 3, \ldots\}$, define $I_i$ as an indicator function that is $1$ if "7" has not occured in rolls $\{1, \ldots, i\}$ and if roll $i$ adds a distinct new number seen. Then $X = \sum_{i=1}^{\infty} I_i$, so: $$ E[X] = \sum_{i=1}^{\infty} E[I_i] =\sum_{i=1}^{\infty} Pr[I_i=1]=\sum_{i=1}^{\infty} (5/6)^{i}\sum_{j\neq 7} p_j(1-p_j)^{i-1} $$ where we define $p_j$ as the conditional probability that a given roll is $j$, given that it is not 7. So $p_1 = \frac{1/36}{5/6}$, $p_2=\frac{2/36}{5/6}$, $p_3=\frac{3/36}{5/6}$, and so on, with $p_1=p_{12}$, $p_2=p_{11}$, and so on. Thus: \begin{align} E[X] &= \sum_{i=1}^{\infty} (5/6)^{i}\left(2\sum_{j=2}^6p_j(1-p_j)^{i-1}\right)\\ &=\sum_{j=2}^6 \frac{p_j}{1-p_j}\sum_{i=1}^{\infty} [(5/6)(1-p_j)]^i\\ &=\sum_{j=2}^6 \frac{p_j}{1-p_j}\left(\frac{(5/6)(1-p_j)}{1-(5/6)(1-p_j)}\right)\\ &=\sum_{j=2}^6 \frac{p_j(5/6)}{1-(5/6)(1-p_j)}\\ &\approx 3.161472 \end{align}


I wrote a C program to simulate over $10^8$ independent experiments. The simulation shows the average number of distinct numbers seen before 7 is $\approx 3.161488$ (very good match to the above exact answer), and a success probability of $\theta \approx 0.005252$, $1/\theta = 190.384$. So, assuming my simulation for successes had no bugs, the answer is that about 1 out of every 190 times you will get a success (where a success is defined as getting all other numbers before 7).

$\endgroup$
8
  • $\begingroup$ I like where you're going (and thanks for walking me through that 1st baby step... it's not as intuitive as it looks when you've never seen it before); let's step out into the deeper water now.... We can't keep "pretending" the rest of the numbers have equal probability, they don't. Also, we don't know in what order they'll appear. My thinking suggests it doesn't matter what order they appear, so long as 7 appears last. May we assume order doesn't matter, then assume a given order of appearance? That was one of the paths that led me astray before I started researching and asking for help.... $\endgroup$ – reubix_part3 Jun 5 '15 at 2:16
  • 1
    $\begingroup$ The problem is that if "2" appears early, then we are happy since that was the least likely one (its probability is 1/36). All of the different orderings of occurrence make the problem hard. That is why symmetry (assuming equal probabilities) makes it easier. $\endgroup$ – Michael Jun 5 '15 at 2:24
  • $\begingroup$ My answer now contains the exact probability. $\endgroup$ – Yuval Filmus Jun 5 '15 at 4:02
  • 1
    $\begingroup$ @reubix_part3 , Yuval's answer is using Markov chain theory which is a bit more advanced. Another answerer gives you a method via inclusion-exclusion principle of probability (the computations get longer and longer). My approach was to change the problem to get an answer that looked nice and simple. I simulated to make sure my math for $E[X]$ was error-free, and along the way it was easy enough to also get the simulated win probability. Yuval's work gives me confidence that I had no bugs. There is no "math" behind a simulation, though I can send you the C program I used if you like. $\endgroup$ – Michael Jun 5 '15 at 20:15
  • 1
    $\begingroup$ I did a "for" loop over $10^8$ experiments. Each experiment involved rolling the die repeatedly until we either win, or we see a "7." Every time I rolled, I summed the numbers and placed the resulting sum into a binary vector $seen[]$, so that $seen[i]=1$ if and only if we have seen a sum of $i$. I also had a counter that incremented every time we saw something new (we know it is new if, when we go to change seen[i], we find that it was 0 but we change it to 1). If we see 10 things new before 7, we win. The win probability is found by taking the total number of wins and dividing by $10^8$. $\endgroup$ – Michael Jun 5 '15 at 20:23
4
$\begingroup$

You can compute the probability exactly if you really want (see below), but it's probably not worth it. Instead, you can estimate it to your heart's content by simulation – just run the game many many times, and see how often do you win.

In order to compute the probability exactly, the first step is to find an economical way to describe the state of the game. Naively, there are $2^{10} = 1024$ possible states, but we can reduce it to $3^5 = 243$ by grouping the numbers into pairs: $(2,12),(3,11),(4,10),(5,9),(6,8)$. The state identifies how many numbers in each pair are crossed.

Now form a $243\times 243$ transition matrix $A$ in which $A_{st}$ is the probability to move from state $s$ to state $t$. The probabilities out of state $s$ don't sum to $1$ since it's possible to lose the game. We assume that once at the winning state $W$, the next move always loses.

Let $v_I$ be the indicator vector of the initial state, and $v_W$ the indicator vector of the winning state. The probability to win in exactly $n$ moves is $v'_I A^n v_W$, and so the winning probability is $$ \sum_{n=0}^\infty v'_I A^n v_W = v'_I \sum_{n=0}^\infty A^n v_W = v'_I (I-A)^{-1} v_W. $$ You can write a program that computes the matrix $A$ (with rational entries), and then use a linear algebra package that supports rational numbers to calculate the exact probability. It could turn out the the exact probability is a very complicated number – with very large numerator and denominator, but the computer can probably deal with it given enough time.

Update: The exact winning probability is $$ \frac{126538525259}{24067258815600} \approx 0.00525770409619644.$$ This number agrees with the simulation results by both myself and Michael.

Note that the matrix in question is triangular, so the computation is pretty fast. We can interpret the matrix $I - A$ in the following way: $(I-A)_{ss}$ is the probability of losing while at state $s$, and $(I-A)_{st}$ is minus the probability of moving from $s$ to $t$; we assume that after reaching the winning state, we immediately lose.

$\endgroup$
9
  • $\begingroup$ I'm too uninformed in this field to follow the math you're showing, Yuval. I did create a spreadsheet simulator to try to get an impression of the game's behavior over long runs, but it's up/down/up/down/up/down. With the very long odds against and the massive payout on a win, you'd have to run it to resolution millions of times to even out the fluctuations. I don't have access to that kind of a processor... I can share the spreadsheet formulas if anyone's interested in that.... $\endgroup$ – reubix_part3 Jun 5 '15 at 2:51
  • 2
    $\begingroup$ My simulation gives 0.005251 $\pm$ 0.000003, based on $10^9$ experiments that took about 2 minutes to run. $\endgroup$ – Yuval Filmus Jun 5 '15 at 3:06
  • 1
    $\begingroup$ I implemented my algorithm and calculated the exact probability. $\endgroup$ – Yuval Filmus Jun 5 '15 at 4:02
  • 2
    $\begingroup$ I did a calculation in R with three vectors with $11$ entries and two with $2^{11}=2048$, in effect looping once through the states with a stored recursion rather than a matrix to find the probability of visiting each one. The probabilities for the final dice-roll ($2-12$) collected were 0.322429042 0.103510405 0.042134184 0.019486740 0.009810776 0.005257704 0.009810776 0.019486740 0.042134184 0.103510405 0.322429042 and the value for the final value seen being $7$ was about $0.005257704$, which agrees with your calculation. $\endgroup$ – Henry Jun 5 '15 at 13:44
  • 1
    $\begingroup$ @Michael I calculated it. It's not so difficult. At any given state, you consider all 11 possible dice rolls, and see which state they put you in. $\endgroup$ – Yuval Filmus Jun 7 '15 at 21:52
2
$\begingroup$

You can do this exactly in a straightforward fashion using the inclusion-exclusion principle to compute 1 minus the probability of getting a 7 before at least one of the other numbers. You can find a real easy-to-follow write up of how to get the probability of numbers before other numbers using inclusion-exclusion in the last answer here which also describes how to get the average number of rolls. Doing it for all the numbers is tedious, but that's what computers are for. That page also links to my own explanation and an R script on another site which computes the terms with the help of a combn function. The probability you want is 1 minus the last probability computed by that R script which to 15 places is $0.00525770409617443$.

We will be computing 1 minus the probability of a 7 occurring before one or more of the other numbers. To compute this probability, first sum the probabilities of a 7 occurring before each of the 10 numbers. This over counts the cases where we get it before more than just 1 number. So we then subtract the sum of the probabilities that it can occur before each combination of 2 of the other numbers. Then we add back the probability that it can occur before each combination of 3 other numbers, and so on. That's inclusion-exclusion.

Mathematically we have:

$$ \text{P(roll all $a_n$ for $n \neq N$ before $a_N$) = }1-\sum_{j=1}^{|S|-1}\sum_{k=1}^{|S|-1 \choose j}(-1)^{j+1}\frac{S_N}{S_N+\sum_{i=1}^jC_{i,k}} $$ where $$ S = \{S_n: S_n=36P(a_n)\} $$ gives the set of numbers of ways to roll $a_n$ out of 36, and $C$ is a matrix whose columns are the combinations of size $j$ from $S$ excluding $S_N$. That is

$$ C = \mathrm{Combn}((S - \{S_N\},j)). $$

For example, if we want the probability of rolling all the numbers before a 7, then we would have $S=\{1,1,2,2,3,3,4,4,5,5,6\}$ with $S_N = 6$ since $P(7) = 6/36$, and $a_N = 7$.

The following R script implements this for the probability of rolling all numbers before a 7:

S = c(1,1,2,2,3,3,4,4,5,5,6)  # Wynn bet
# S = c(1,2,3,4,5,6)          # All tall or all small
N = length(S)
p = 0
for (j in 1:(N-1)) {
  C = combn(S[1:(N-1)],j)
  for (k in 1:choose(N-1,j)) {
    p = p + (-1)^(j+1) * S[N]/(S[N] + sum(C[1:j,k]))
  }
}
1-p

Output:

> 1-p
[1] 0.00525770409617443

You can do this for the all small or all tall bet by simply uncommenting the line that replaces S with $\{1,2,3,4,5,6\}$. This gives to 15 digits $0.0263539092486457$.

$\endgroup$
1
  • 1
    $\begingroup$ I added the inclusion-exclusion formula and simplified R script so this answer is now self-contained here. I also gave more digits in the result which was truncated previously, and I provided the answer for the all tall and all small bets. This provides a good alternative to generating and inverting a large matrix, requiring only the services of a combn function while being conceptually simple. $\endgroup$ – BruceZ Jun 8 '15 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.