States and recursion: random walks and Markov chains

Some interview questions describe a process with no fixed length: a price that wanders until it hits a stop, a game that ends only when someone leads by two, coin flips until a pattern shows up, a server that moves between states every minute. You cannot list the outcomes, so counting fails. What works is to name the states, write one equation per state about what happens after a single step, and solve. After this lesson you will be able to set up those equations in under a minute, solve random walks with two exits, find the expected wait for a coin pattern, and compute how much of the time a Markov chain spends in each state.

One equation per state

The method is called first-step analysis. It has four moves:

1. Choose states so that the future depends only on the current state, not on how you got there.

2. Name one unknown per state: the probability of ending at the target, or the expected number of steps left.

3. Condition on the next step. For a probability, each unknown is the sum over next states of P(move) × that state's unknown. For expected steps, add 1 for the step you just spent.

4. Pin the ends, the states where the process stops, and solve.

Here it is on a trade. Your position shows $2 of profit. Each minute the price moves your profit up or down $1 with equal chance. You close the trade at $5 of profit or at $0, whichever comes first. Let h_k be the chance of closing at $5 when your profit is k dollars.

| k = 1 to 4 | h_k = (h_(k−1) + h_(k+1))/2 |