Expected Rolls for a Consecutive 4-5 Sequence
You roll a fair six-sided die repeatedly. What is the expected number of rolls until you first see a 4 immediately followed by a 5?
Hints
- Define two states: "no useful recent roll" and "just rolled a 4." Write an equation for each.
- When you just rolled a 4, a subsequent 4 keeps you in the promising state rather than resetting -- this is the subtle part.
- Set up the system: $E = 1 + \frac{5}{6}E + \frac{1}{6}E_4$ and $E_4 = 1 + \frac{1}{6}(0) + \frac{1}{6}E_4 + \frac{4}{6}E$. Solve for $E$.
Worked Solution
How to Think About It: This is a pattern-matching problem on a sequence of die rolls. You are waiting for the specific consecutive pair (4, 5). The trick is that the problem has memory: if you just rolled a 4, your next roll matters a lot -- a 5 finishes the game, another 4 keeps you in a "promising" state, and anything else resets you. Set up states based on whether your most recent roll was a 4 or not.
Quick Estimate: The probability of any two consecutive rolls being (4, 5) is $1/36$. If the attempts were independent, you would need about 36 rolls. But attempts overlap (each new roll starts a new potential pair), and rolling a 4 after a 4 keeps you in the game rather than resetting. So the answer should be close to 36, maybe exactly 36.
Approach: Define states and use the law of total expectation.
Formal Solution:
Let $E$ be the expected number of rolls from the start (no useful recent roll) and $E_4$ be the expected additional rolls given that you just rolled a 4.
From the start state: On the first roll, with probability $1/6$ you roll a 4 (entering state $E_4$), and with probability $5/6$ you roll something else (staying in the start state). Each roll costs 1:
$$E = 1 + \frac{5}{6}E + \frac{1}{6}E_4$$
From the "just rolled 4" state: On the next roll: - With probability $1/6$, you roll a 5 -- done. Cost: 1 more roll. - With probability $1/6$, you roll another 4 -- stay in state $E_4$. Cost: 1 more roll. - With probability $4/6$, you roll something other than 4 or 5 -- reset to start. Cost: 1 more roll.
$$E_4 = 1 + \frac{1}{6}(0) + \frac{1}{6}E_4 + \frac{4}{6}E$$
Note: the $0$ is because if you roll a 5, you need 0 additional rolls after this one (the 1 at the front already counts this roll).
So: $E_4 = 1 + \frac{1}{6}E_4 + \frac{4}{6}E$
Solving for $E_4$:
$$\frac{5}{6}E_4 = 1 + \frac{4}{6}E \implies E_4 = \frac{6}{5} + \frac{4}{5}E$$
Substituting into the equation for $E$:
$$E = 1 + \frac{5}{6}E + \frac{1}{6}\left(\frac{6}{5} + \frac{4}{5}E\right)$$
$$E = 1 + \frac{5}{6}E + \frac{1}{5} + \frac{4}{30}E$$
$$E = \frac{6}{5} + \frac{5}{6}E + \frac{2}{15}E$$
$$E = \frac{6}{5} + \left(\frac{25}{30} + \frac{4}{30}\right)E = \frac{6}{5} + \frac{29}{30}E$$
$$E - \frac{29}{30}E = \frac{6}{5}$$
$$\frac{1}{30}E = \frac{6}{5}$$
$$E = 36$$
Answer: The expected number of rolls is $E = 36$. This matches the naive estimate of $1/(1/36) = 36$ -- in this particular case, the overlapping structure and the "4 after 4" effect exactly cancel out, giving the same answer as if attempts were independent.
Intuition
Pattern-matching problems on random sequences are best solved with Markov states that track progress toward the target pattern. The key subtlety here is what happens when you roll a 4 while already in the "just rolled 4" state -- you do not reset to the beginning; you stay in the promising state. For the pattern (4, 5), this effect is mild (only one overlap possibility), and the answer turns out to be exactly 36.
For more complex patterns, the answer can differ significantly from $1/P(\text{pattern})$. For example, the expected time to see (6, 6) is $6 \times 6 + 6 = 42$, not 36, because after rolling a 6, another 6 makes progress toward the next attempt rather than being wasted. The Conway leading number technique or Markov chain methods generalize this to arbitrary patterns.