First-Step Analysis

First-step analysis is the workhorse technique for a huge family of interview questions: "how likely is this to happen before that?" and "how long, on average, until it happens?" The idea is almost embarrassingly simple. You don't know the answer directly, so you condition on the one thing you can reason about — what happens on the very first step — and use the fact that after that step you're facing a smaller version of the same problem. That self-reference turns the question into an equation you can solve.

It's nothing more than the The Law of Total Probability (for probabilities) or its cousin for expectations, applied one step at a time. But naming the move and drilling it is what makes hard-looking Markov questions fall over in two lines.

The recipe

Let $h_i$ be the quantity you want — a probability of reaching some goal, or an expected time — starting from state $i$. Condition on the first transition: from $i$ you move to state $j$ with probability $P_{ij}$, and from $j$ you face the same problem with value $h_j$. That gives one equation per state:

$$h_i = \sum_j P_{ij}\, h_j \qquad(\text{for a hitting probability}),$$ $$h_i = 1 + \sum_j P_{ij}\, h_j \qquad(\text{for an expected time}).$$

The only difference is the $+1$: computing a time, you charge yourself one step for having taken the first move, then add the expected time remaining. Pin down the boundary conditions — the values at the absorbing states you're measuring to — and you have a small linear system. Solve it.

Worked example: waiting for two heads in a row

Flip a fair coin until you see two heads in a row (HH). How many flips on average? Set up three states by how much progress you've made toward HH:

• S — no useful progress (start, or you just flipped a tail).
• A — the last flip was a heads (one away from done).
• HH — done. This is the absorbing state; its expected remaining time is $0$.

Let $m_S$ and $m_A$ be the expected flips to reach HH from each state. Reading the transitions off the diagram and charging $+1$ per flip:

$$m_S = 1 + \tfrac12 m_A + \tfrac12 m_S, \qquad m_A = 1 + \tfrac12 \cdot 0 + \tfrac12 m_S .$$

From the first equation, $\tfrac12 m_S = 1 + \tfrac12 m_A$, so $m_S = 2 + m_A$. Substitute into the second: $m_A = 1 + \tfrac12(2 + m_A) = 2 + \tfrac12 m_A$, giving $\tfrac12 m_A = 2$, so $m_A = 4$ and $m_S = 6$. On average it takes 6 flips to see two heads in a row.

The surprise: waiting for HT instead takes only 4 flips. The same recipe on the HT machine gives $4$, because a tail after a head completes the pattern instead of destroying your progress. Patterns that can overlap themselves (like HH) take longer to appear — a genuinely counterintuitive result that first-step analysis makes obvious.

Worked example: gambler's ruin in one line

The same method derives the Gambler's Ruin result cleanly. Let $h_i$ be the probability of reaching $N$ before $0$ from bankroll $i$, with a fair coin. Conditioning on the first bet:

$$h_i = \tfrac12\, h_{i+1} + \tfrac12\, h_{i-1}, \qquad h_0 = 0,\; h_N = 1 .$$

This says $h_i$ is the average of its neighbors, which forces the solution to be a straight line, and the only straight line hitting $0$ at $0$ and $1$ at $N$ is $h_i = i/N$. The famous ruin probability drops straight out of the recipe.

Where it fits

First-step analysis is the elementary, no-machinery route to results that optional stopping reaches with martingales. It computes hitting probabilities, expected absorption times, and expected rewards for any Markov chain, and it's the fastest tool to reach for the moment a problem mentions "first time" or "before."