Pattern recurrence

FreeProbabilityEasyJane StreetSIGFive Rings

A fair standard die is rolled until two consecutive 11s first appear. Find the expected number of rolls.

Solution

High-level idea

Model the process as a Markov chain with two transient states tracking the current "run" of consecutive 1s. Set up first-step equations and solve the 2×22\times 2 linear system.

States and equations

Let p=16p = \tfrac{1}{6} be the probability of rolling a 1. Define:

  • S0S_0: start, or the last roll was not a 1.
  • S1S_1: the last roll was a 1 (one consecutive 1 in progress).

Let μ0,μ1\mu_0,\mu_1 be the expected number of additional rolls needed to reach absorption (two consecutive 1s) from each state.

From S0S_0 — one roll is used; with probability 16\tfrac{1}{6} we move to S1S_1, with probability 56\tfrac{5}{6} we remain in S0S_0:

μ0=1+16μ1+56μ0.\mu_0 = 1 + \frac{1}{6}\mu_1 + \frac{5}{6}\mu_0.

From S1S_1 — one roll is used; with probability 16\tfrac{1}{6} we finish (0 more rolls), with probability 56\tfrac{5}{6} we return to S0S_0:

μ1=1+56μ0.\mu_1 = 1 + \frac{5}{6}\mu_0.

Solving the system

Rearranging the first equation:

μ056μ0=1+16μ1    μ0=6+μ1.\mu_0 - \frac{5}{6}\mu_0 = 1 + \frac{1}{6}\mu_1 \implies \mu_0 = 6 + \mu_1.

Substituting μ1=1+56μ0\mu_1 = 1 + \tfrac{5}{6}\mu_0:

μ0=7+56μ0    16μ0=7    μ0=42.\mu_0 = 7 + \frac{5}{6}\mu_0 \implies \frac{1}{6}\mu_0 = 7 \implies \mu_0 = 42.

Check: μ1=1+56(42)=36\mu_1 = 1 + \tfrac{5}{6}(42) = 36, and 6+36=426 + 36 = 42. ✓

Final answer

The expected number of rolls is 42\boxed{42}.

Related problems