Most interview problems that need a Markov chain do not announce themselves. The skill is recognising one.
The definition that matters
A process is Markov if the next state depends only on the current state, not on the path that got you there. That is the property that makes the algebra tractable.
Choosing states is the whole problem
Consider: expected number of fair coin flips to see the pattern HTH.
The naive state is "number of flips so far", which is useless. The right states describe progress toward the pattern:
- S0: no useful progress
- S1: just saw H
- S2: saw HT
- S3: saw HTH (done)
Now write one equation per state, each conditioning on the next flip. From S2, a head finishes; a tail sends you back to S0. From S1, a tail advances to S2; a head keeps you at S1 (the new H restarts progress). And so on.
Solving gives 10 flips.
Compare with HTT, which gives 8, and HHH, which gives 14. Different patterns take different times despite each having probability 1/8 in three flips - a result that reliably surprises candidates and is a favourite follow-up.
Expected hitting times
The general recipe: let E_i be the expected steps to reach the target from state i. For each non-target state write
E_i = 1 + sum over j of P(i to j) times E_j
and set E = 0 at the target. Solve the linear system. In interviews it is rarely more than three equations.
Stationary distributions
For "in the long run, what fraction of time is spent in each state", solve pi = pi P with the entries summing to 1.
For a random walk on a graph, there is a shortcut worth knowing: the stationary probability of a vertex is proportional to its degree. That turns some intimidating-looking questions into one line.
Check memorylessness
Not every process is Markov in the state you chose. If the answer depends on how you arrived, you need a richer state - which is usually the fix when your equations come out inconsistent.
Practise in stochastic processes.