How do I calculate the odds of a given set of dice results occurring before another given set?

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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