Expected Rolls to Reach Position 10 in a Symmetric Random Walk
You start at position $0$ on the number line. Each turn, you roll a fair six-sided die and get a result $X$.
- If $X \in \{1, 2, 3\}$, you move $X$ steps to the right.
- If $X \in \{4, 5, 6\}$, you move $X - 3$ steps to the left (i.e., 1, 2, or 3 steps left).
The process ends when you first reach position $10$ or higher. How many rolls does it take on average?
Hints
- Compute the expected displacement per roll. What does it being zero tell you about the type of random walk?
- The variance per step is $\sigma^2 = \frac{1}{6}(1^2 + 2^2 + 3^2 + 1^2 + 2^2 + 3^2) = 14/3$, and the diffusion scale $d^2/\sigma^2$ is tempting. Before using it, ask what boundary condition that formula assumes -- it is an *exit* time from a bounded region, and this walk has no lower boundary at all.
- Set up the recurrence $E_i = 1 + \frac{1}{6}(E_{i+1} + E_{i+2} + E_{i+3} + E_{i-1} + E_{i-2} + E_{i-3})$ with boundary $E_i = 0$ for $i \ge 10$, and impose a reflecting or absorbing lower boundary to make the system finite.
Worked Solution
How to Think About It: Each roll gives a displacement drawn uniformly from $\{-3, -2, -1, +1, +2, +3\}$, so the mean step is $0$: this is a symmetric (driftless) random walk with variable step sizes. The question asks for the expected time to first reach $+10$, and there is no lower boundary -- the walk may wander arbitrarily far negative.
That last fact is the whole problem. Two different things are true at once and it is easy to conflate them: a driftless walk on $\mathbb{Z}$ is *recurrent*, so it hits $+10$ with probability $1$; but the time it takes has a heavy $t^{-3/2}$ tail, so the *expectation* of that time diverges. "Certain to happen" and "happens in finite expected time" are not the same statement. The trap the question is built around is reaching for the diffusion scale $d^2/\sigma^2$, which silently answers a bounded problem instead.
Quick Estimate: For a symmetric random walk, the variance per step is: $$\sigma^2 = E[\Delta^2] = \frac{1}{6}(1 + 4 + 9 + 1 + 4 + 9) = \frac{28}{6} = \frac{14}{3} \approx 4.67$$
By diffusion approximation, the position after $n$ steps is approximately $N(0, n\sigma^2)$. The probability of being at or above 10 after $n$ steps is roughly $\Phi(-10/\sqrt{n \cdot 14/3})$. For this to be significant, we need $n$ of order $100/\sigma^2 \approx 21$.
That $\approx 21$ figure is exactly the trap. The formula $d^2/\sigma^2$ prices an *exit* time from a bounded region, so it answers a two-barrier problem, not the one-sided problem posed here.
Approach: Set up a system of linear equations. Let $E_i$ be the expected number of rolls to reach position $\ge 10$ starting from position $i$. For $i \ge 10$, $E_i = 0$. For $i < 10$:
$$E_i = 1 + \frac{1}{6}\bigl(E_{i+1} + E_{i+2} + E_{i+3} + E_{i-1} + E_{i-2} + E_{i-3}\bigr)$$
The problem is that $i$ can be arbitrarily negative, giving infinitely many states. For a symmetric walk with no lower barrier, $E_0 = \infty$ (this is a well-known result: the expected first-passage time to a one-sided barrier for a mean-zero random walk is infinite, even though the walk will reach the barrier with probability 1).
Diffusion approximation (finite answer): If we instead treat this as a diffusion and ask for the expected time conditional on reaching $+10$ before $-10$ (a symmetric two-barrier problem), then by the standard result for a Brownian motion between barriers at $-a$ and $+a$:
$$E[\tau \mid \text{hit } +a \text{ first}] = \frac{a^2}{\sigma^2}$$
With $a = 10$ and $\sigma^2 = 14/3$:
$$E[\tau] \approx \frac{100}{14/3} = \frac{300}{14} \approx 21.4$$
Finite-state solutions (what a lower boundary actually buys you): Add a boundary at $0$ and the expectation becomes finite and computable. States $0, \ldots, 9$ with everything $\geq 10$ absorbing gives a $10 \times 10$ linear system; solving it in exact rational arithmetic:
- clamped at $0$ (a step that would go below $0$ leaves you at $0$): $E_0 = \tfrac{95956}{3315} \approx 28.95$
- reflecting at $0$ (position $\mapsto |{\cdot}|$): $E_0 = \tfrac{7085976}{294881} \approx 24.03$
- symmetric two-barrier, absorbing at $+10$ and $-10$: $E_0 = \tfrac{7085976}{294881} \approx 24.03$ as well -- the same number, as it must be, since folding the symmetric two-barrier walk about the origin *is* the reflecting walk
All of these exceed the diffusion estimate $300/14 \approx 21.4$, which ignores overshoot past the barrier. None of them is the answer to the question as posed -- they are the answers to the neighbouring questions the trap quietly substitutes.
Answer: No -- the candidate's "about $21$ rolls" is wrong for the game as stated. For a mean-zero walk with no lower barrier, the walk reaches $10$ with probability $1$, but the expected first-passage time is infinite: $E[\tau] = \infty$. The diffusion figure $\frac{300}{14} \approx 21.4$ (from $E[\tau] \approx d^2/\sigma^2$ with $\sigma^2 = 14/3$, $d = 10$) answers a *different* problem -- one with a second absorbing barrier or a reflecting barrier at the origin -- and quoting it here is precisely the pitfall this question probes. Simulation confirms the divergence: the truncated mean $E[\min(\tau, T)]$ grows like $\sqrt{T}$ without bound (roughly $220$, $460$, $910$ for $T = 10^3,\ 4\times 10^3,\ 1.6\times 10^4$).
Intuition
This problem illustrates a subtle point about symmetric random walks. While the walk will reach any target with probability 1 (recurrence), the expected time to reach a one-sided target is infinite for a mean-zero walk -- you keep getting pulled back by symmetry. A finite answer arises only in modified games -- imposing a lower boundary, or switching to a two-barrier problem; solved exactly, those come out around $24$ rolls (reflecting at $0$, equivalently absorbing at $\pm 10$) or $29$ rolls (clamped at $0$), with the $\approx 21$ diffusion figure sitting below both because it ignores overshoot. For the one-sided game as stated, the expected number of rolls is infinite.
The diffusion shortcut $E[\tau] \approx d^2/\sigma^2$ is extremely handy for interview estimation. It says the expected hitting time scales as the square of the distance divided by the step variance. Doubling the target distance quadruples the expected time. The step variance $14/3$ is notably larger than for a simple $\pm 1$ walk (which has $\sigma^2 = 1$), so you reach the target faster per step -- but you also have more volatility and more overshoot.