1
$\begingroup$

There's a push-your-luck dice game called Can't Stop where you roll four six-sided dice, group the dice into pairs of your choice, then advance tokens along paths corresponding to the sums of your pairs. For example, if you roll (2, 3, 4, 5), you can advance two tokens one space each along paths 5 and 9 or paths 6 and 8, or you can advance one token two spaces on path 7. The goal is to get your tokens to the ends of the paths.

Each path is a different length. Paths 2 and 12 are 3 spaces long, paths 3 and 11 are 5 spaces long, ..., and path 7 is 13 spaces long. So although you're less likely to roll 2s and 12s, you don't have to roll them as often to reach the end.

You have a limited number of tokens (3), and if you ever roll your dice and can't use them to advance any of your tokens, you have to remove your tokens and start over.

There are other rules that complicate things, but my question is about the relationship between how often you're likely to roll a given number compared to how long the path is, and therefore which paths are easiest to complete. So I decided to simplify things by pretending you can only have one token on the board at a time, and if you can't advance that token, you fail and start over (with the same path).

The first thing I tried was this: for each path, I figured out the probability of rolling at least one success on a given roll. Then I raised that probability to the power of the number of spaces in the path to find the probability of succeeding that many times in a row.

That's not quite good enough, though, because it ignores cases where you get two successes in a single roll. So I figured out the expected number of successes per roll for each path (or at least I think I did). But expected successes are different from probability of success, so I can't just use the number of spaces in each path as exponents like in the previous paragraph, right?

What I'm looking for is a way to get from knowing the expected number of successes in a given roll to knowing how likely it is that you'll have N successes without ever failing. Or if I'm asking the wrong question, I'd like to be corrected. :)

Thanks!

$\endgroup$

1 Answer 1

0
$\begingroup$

You can't deduce the probability of $N$ successes without failing from the expected number of successes in a given roll. To see that, compare two situations where a) you're certain to get exactly one success per roll and b) you have probability $0.5$ each of getting $0$ or $2$ successes per roll. The expected number of successes per roll is the same in the two cases, but in a) you'll go on forever without ever failing, and in b) you'll fail on every second roll.

So we need to work with probabilities from the beginning. If I interpret your description of the game correctly, we select a number $2\le k\le12$, and then in each roll we roll four six-sided dice and try to form pairs that sum to $k$; for each pair we advance by one square, and we're looking for the probability of advancing $N$ squares before failing to form any pairs in a roll.

So we need the numbers $a_{kj}$ of different rolls that allow $j=0,1,2$ pairs summing to $k$ to be formed. I see two ways of doing that: by computer, or by inclusion-exclusion. So let's try doing it by inclusion-exclusion and then check the result by computer.

There are three ways to group four dice into two pairs. To calculate $a_{k2}$ we need the numbers $b_{kj}$ for $j=1,2,3$ of rolls in which $j$ particular groupings yield two sums of $k$. Fortunately the three pairs of the three groupings all have equivalent overlap, so we only need to deal with one type of overlap in this case. Let's denote by $\sigma_k$ the number of ways that a pair can sum to $k$:

$$ \sigma_k=\begin{cases}k-1&2\le k\le7\;,\\13-k&7\lt k\le12\;.\end{cases} $$

Then the number of ways for a given one of the groupings to yield two sums of $k$ is $b_{k1}=\sigma_k^2$. For the overlap of two groupings, let's consider the groupings $\underbrace{rs}\underbrace{tu}$ and $\overbrace{r\underbrace{st}u}$. Then we have

$$ r+s=k\;,\\ t+u=k\;,\\ r+u=k\;,\\ s+t=k\;. $$

This yields $t=r$ and $u=s$, so we have $b_{k2}=\sigma_k$ ways to choose $r$ and $s$, which also fixes $t$ and $u$.

For all $3$ groupings to yield two sums of $k$, we need to additionally have

$$ r+t=k\;,\\ s+u=k\;, $$

which implies $r=s=t=u=k/2$, for which there are $b_{k3}=\pi_k$ ways, where $\pi_k$ is $1$ for $k$ even and $0$ for $k$ odd.

Now inclusion-exclusion yields

$$a_{k2}=3b_{k1}-3b_{k2}+b_{k3}=3\sigma_k^2-3\sigma_k+\pi_k=3\sigma_k(\sigma_k-1)+\pi_k\;,$$

which works out as

$$ \begin{array}{c|cc} k&2&3&4&5&6&7\\\hline \sigma_k&1&2&3&4&5&6\\ \pi_k&1&0&1&0&1&0\\ a_{k2}&1&6&19&36&61&90 \end{array} $$

and correspondingly mirrored for $k\gt7$.

The calculation for $a_{k0}$ and $a_{k1}$ is only slightly more involved. I won't write out as many details; the basic ideas are the same; every combination of pairs constrains some or all of the numbers to be equal.

There are $6$ possible pairs. There are $36\sigma_k$ rolls in which a particular pair sums to $k$.

Two different pairs can either overlap or not. If they do, that constrains the two non-overlapping numbers to be equal, so there are $6\sigma_k$ rolls. If they don't, both pairs must separately sum to $k$, which gives $\sigma_k^2$ rolls.

Three different pairs can either cover all four numbers, in which case one pair fixes the other two numbers, leaving $\sigma_k$ rolls, or they can cover only three numbers, in which case those numbers have to be equal and the fourth is free, leaving $6\pi_k$ rolls.

Four different pairs can be viewed as three pairs covering all four numbers, and one more pair that either, if the two missing pairs are disjoint, just reiterates a constraint already implied by the three pairs ($\sigma_k$ rolls) or, if the two missing pairs overlap, forces all four numbers to be equal ($\pi_k$ rolls).

For five or six different pairs to sum to $k$, all four numbers have to be equal ($\pi_k$ rolls).

Then taking into account the numbers of ways of choosing such combinations of pairs, inclusion-exclusion yields

\begin{eqnarray} a_{k0}&=&1296-6\cdot36\sigma_k+12\cdot6\sigma_k+3\cdot\sigma_k^2-16\cdot\sigma_k-4\cdot6\pi_k+3\sigma_k+12\pi_k-6\pi_k+\pi_k\\ &=&1296-157\sigma_k+3\sigma_k^2-17\pi_k\;. \end{eqnarray}

Then $a_{k1}$ follows from $\sum_ja_{kj}=6^4$, and the result is

$$ \begin{array}{c|cc} k&2&3&4&5&6&7\\\hline a_{k0}&1125&994&835&716&569&462\\ a_{k1}&170&296&442&544&666&744\\ a_{k2}&1&6&19&36&61&90\\ \end{array} $$

Here's Sage code that computes these numbers by enumeration:

def extract (roll,die):
    return roll // 6^(die - 1) % 6 + 1

def sums (roll,pair,k):
    return extract (roll,pair [0]) + extract (roll,pair [1]) == k

def a (k):
    counts = [0,0,0]
    for roll in (0..1295):
        max = 0
        for pairs in [[[1,2],[3,4]],[[1,3],[2,4]],[[1,4],[2,3]]]:
            npairs = 0
            for pair in pairs:
                if sums (roll,pair,k):
                    npairs = npairs + 1
            if npairs > max:
                max = npairs 
        counts [max] = counts [max] + 1
    return counts

[a(k) for k in (2..7)]

(Full disclosure: There was one error in the inclusion-exclusion calculation before I checked it against the computed numbers.)

The corresponding probabilities are $a_{kj}/6^4$. What remains is to sum these probabilities over all ways of reaching $N$ without failing. You didn't specify what happens when you overshoot the end of the path – if that's not allowed, we need the probably $p_{kN}$ of landing on the $N$-th square; if it is, we need $p_{kN}+p_{k,N-1}a_{k2}/1296$. The $p_{kN}$ can be determined as the coefficients of a generating function:

$$ p_{kN}=[x^N]\frac1{1-(a_{k1}x+a_{k2}x^2)/1296}\;, $$

where $[x^N]$ denotes extracting the coefficient of $x^N$ in the series expansion at $x=0$. For instance, the probability of advancing by exactly $N=5$ squares for $k=4$ is

$$ p_{45}=\frac{818096269133}{114254951251968}\simeq0.7\%\;. $$

Here's Sage code to compute these probabilities:

def p (k,N):
    return taylor (1 / (1 - (a (k) [1] * x + a (k) [2] * x^2) / 1296),(x,0),N+1).coefficients (sparse=false) [N]

Here's a table of the $p_{kN}$ for $k=2,\ldots,7$ and $N=1,\ldots,13$ (up to the greatest path length in your game):

\begin{array}{c|cc} N\setminus k&2&3&4&5&6&7\\\hline 1&0.1312&0.2284&0.3410&0.4198&0.5139&0.5741\\ 2&0.0180&0.0568&0.1310&0.2040&0.3111&0.3990\\ 3&0.0025&0.0140&0.0497&0.0973&0.1841&0.2689\\ 4&0.0003&0.0035&0.0189&0.0465&0.1092&0.1821\\ 5&0.0000&0.0009&0.0072&0.0222&0.0648&0.1232\\ 6&0.0000&0.0002&0.0027&0.0106&0.0384&0.0834\\ 7&0.0000&0.0001&0.0010&0.0051&0.0228&0.0564\\ 8&0.0000&0.0000&0.0004&0.0024&0.0135&0.0382\\ 9&0.0000&0.0000&0.0001&0.0012&0.0080&0.0258\\ 10&0.0000&0.0000&0.0001&0.0006&0.0048&0.0175\\ 11&0.0000&0.0000&0.0000&0.0003&0.0028&0.0118\\ 12&0.0000&0.0000&0.0000&0.0001&0.0017&0.0080\\ 13&0.0000&0.0000&0.0000&0.0001&0.0010&0.0054\\ \end{array}

And here's the corresponding table of the probabilities $p_{kN}+p_{k,N-1}a_{k2}/1296$ in case overshoot is allowed:

\begin{array}{c|cc} N\setminus k&2&3&4&5&6&7\\\hline 1&0.1319&0.2330&0.3557&0.4475&0.5610&0.6435\\ 2&0.0181&0.0579&0.1360&0.2156&0.3353&0.4389\\ 3&0.0025&0.0143&0.0516&0.1029&0.1987&0.2966\\ 4&0.0003&0.0035&0.0196&0.0492&0.1179&0.2008\\ 5&0.0000&0.0009&0.0074&0.0235&0.0699&0.1359\\ 6&0.0000&0.0002&0.0028&0.0112&0.0415&0.0919\\ 7&0.0000&0.0001&0.0011&0.0054&0.0246&0.0622\\ 8&0.0000&0.0000&0.0004&0.0026&0.0146&0.0421\\ 9&0.0000&0.0000&0.0002&0.0012&0.0087&0.0285\\ 10&0.0000&0.0000&0.0001&0.0006&0.0051&0.0193\\ 11&0.0000&0.0000&0.0000&0.0003&0.0030&0.0130\\ 12&0.0000&0.0000&0.0000&0.0001&0.0018&0.0088\\ 13&0.0000&0.0000&0.0000&0.0001&0.0011&0.0060 \end{array}

So in your simplified single-path model, path $7$ is the most promising.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .