Expected Rolls – Expected Number of Rolls in a Game of Snakes and Ladders

diceexpected valueprobabilityprobability theory

You are playing a game of snakes and ladders. You start at square $1$, and each turn you roll a $6$ sided dice and move the corresponding number of squares. When you reach at least square $25$, you stop. There is also a snake which connects squares $5$ and $20$ (i.e. if you land on $20$, you immediately move down to $5$), and there is a ladder from $10$ to $15$ (so if you land on 10, you immediately move up to $15$). What is the expected number of rolls until you finish the game? [Source]

If we think about the game without any snakes or ladders, you need to move at least $24$ squares. The expected number you roll on each throw is $3.5$. However, how can you calculate your expected stopping value, when it is likely to be past $25$?

I cannot see how to factor in the probability of hitting the snake or ladder.

Best Answer

Given that this question (and other recent ones from the same OP) comes from a quantitative finance interview prepper, the intention is not to calculate the exact answer but rather a simple estimate – and good estimates are already provided in the source. Since you declared your dislike of the provided answers, however, here's a Markov chain-based method.

Let $E(n)$ be the expected number of rolls needed to get to square $25$ from square $n$. Considering where one roll of the die can take you gives this relation: $$E(n)=1+\frac16(E(n+1)+E(n+2)+E(n+3)+E(n+4)+E(n+5)+E(n+6))$$ …with the provisos that $E(n)=0$ if $n\ge25$ and that if $E(20)$ and $E(10)$ appear they are replaced by $E(5)$ and $E(15)$ respectively. This gives a $24$-variable linear system which can be solved for the final answer $E(0)$ (I've decremented the indices in my SymPy code):

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

# E(0) = 1 + (E(1) + E(2) + ... + E(6)) / 6
# 9 -> 14, 19 -> 4 
A = zeros(24)
for s in range(24):
    A[s,s] += 1
    for r in range(1, 7):
        ns = s+r
        if ns >= 24:
            continue # E(24+) = 0
        if ns == 9:
            ns = 14
        if ns == 19:
            ns = 4
        A[s,ns] -= sixth
b = ones(24, 1)
res = A.LUsolve(b)[0]
print(res)
print(N(res))

The exact answer is $$\frac{2452089490633741}{287565215211072}=8.527072681\ldots$$

Related Question