Probability Theory – Expected Number of Rolls Until All Consecutive Differences Seen

diceexpected valueprobabilityprobability theory

Call a consecutive difference" the absolute value of the difference between two consecutive rolls of a $6$ sided die. For example, the sequence of rolls $143511$ has the corresponding sequence of consecutive differences $31240$. What is the expected number of rolls until all $6$ consecutive differences have appeared?

I can see that there are $6$ possible consecutive differences: $0, 1,…,5$ and they appear among any pair of dice with probability $6/36, 10/36, 8/36, 6/36, 4/36, 2/36$ respectively. However, they could come in all sorts of orders.

I am happy with answers that are close approximations. By simulation the answer is around 25.8.

Best Answer

This can be solved using standard Markov chain methods – let $E(S, r)$ denote the expected rolls needed if the differences in $S$ have been seen and the current roll is $r$ – but an observation is needed to keep the computation time reasonable: the set of seen differences never shrinks, so we can compute expectations six at a time (per each possible $S$) working backwards from $E(\{1,2,3,4,5,6\},r)=0$.

#!/usr/bin/env python3
from itertools import combinations
from sympy import *
sixth = Rational(1, 6)

# E = 1 + (E(null, 1) + E(null, 2) + E(null, 3) + E(null, 4) + E(null, 5) + E(null, 6)) / 6
# E(124, 3) = 1 + (E(124+2, 1) + E(124+1, 2) + E(124+0, 3) + E(124+1, 4) + E(124+2, 5) + E(124+3, 6)) / 6
EV = {(63, r): 0 for r in range(1, 7)}

for t in range(5, -1, -1):
    for seen in combinations(range(6), t):
        seen_n = sum(2**i for i in seen)
        A = zeros(6)
        b = ones(6, 1)
        for curr in range(1, 7):
            A[curr-1,curr-1] += 1
            for ncurr in range(1, 7):
                nseen_n = seen_n | (1 << abs(ncurr-curr))
                if (nseen_n, ncurr) in EV:
                    b[curr-1] += EV[(nseen_n, ncurr)]*sixth
                else:
                    A[curr-1,ncurr-1] -= sixth
        for (curr, x) in enumerate(A.LUsolve(b), 1):
            EV[(seen_n, curr)] = x
finE = 1 + (EV[(0, 1)] + EV[(0, 2)] + EV[(0, 3)]) / 3
print(finE)
print(N(finE, 50))

The final answer is $1+(E(\varnothing,1)+E(\varnothing,2)+E(\varnothing,3))/3$ since $E(S,r)=E(S,7-r)$ by symmetry considerations, or $$\frac{672875275767847611958914137}{26031560987606728347794000}=25.848441\cdots$$

Related Question