How to solve Markov chain and random walk questions

In this article

1. Before you start
2. Why interviewers ask this
3. Markov and random-walk problems from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

The wider set of quant topics is in the quantitative finance interview guide. This page assumes only school-level probability, and the box below lists what to know first.

Why interviewers ask this

A Markov or random-walk question is short to state and hides a method. A coin-flipping game, a drunkard on a corridor or a gambler with a target looks like a puzzle, yet it tests whether you can name the states, write the transitions and turn the story into equations. That is a modelling skill, and it shows quickly whether you reason or recite. The same skills carry into statistics for quant interviews.

A weak answer guesses a number from intuition, or quotes a formula without saying which case it covers. A strong answer defines the states, writes the first-step equations, states the boundary values and checks the result on a small case. A Staff-level answer also says when the formula changes form, for example at a fair game, and what changes if the opponent has unlimited wealth.

If you are preparing for a trading desk, the sales and trading interview questions page covers the wider set of topics around the technical rounds. For the full map of topics, the complete quantitative finance guide is the place to start. If a question asks you to score a prediction, the cross-entropy loss page explains the log-loss idea.

Markov and random-walk problems from first principles

Markov chain

A Markov chain is a random process that moves between a set of states in steps, where the probability of the next state depends only on the current state and not on how the process got there.

Simple random walk

A simple random walk is a Markov chain on the integers in which each step moves up by one with probability p and down by one with probability q, where q equals 1 minus p; more general random walks allow other step sizes.

First-step analysis

First-step analysis is a method that conditions on the first move of a Markov chain to write one linear equation per state for a quantity such as a hitting probability or an expected time.

Stationary distribution

A stationary distribution is a probability vector over the states of a Markov chain that one step of the chain leaves unchanged, so that multiplying it by the transition matrix returns the same vector.

In plain words

Picture a board game where you only look at the square you stand on. The next roll of the dice and the rules of that square decide where you go. It does not matter how you reached the square. That is the whole idea of a Markov chain. The analogy breaks in one place: real games often have memory, such as a card you drew earlier, and a Markov chain does not.

In one precise sentence, the future is independent of the past given the present. The common slip is to drop "given the present". Grinstead and Snell (p. 405-406) put it as: if the chain is in state $s_i$, it moves to state $s_j$ with probability $p_{ij}$, and this does not depend on which states came before.

Step 1: A Markov chain is states plus a transition matrix

A Markov chain is fixed by three things: a set of states, a starting distribution and a transition matrix. A transition matrix is a table whose entry in row i and column j is the probability of moving from state i to state j in one step, so each row sums to 1. Grinstead and Snell call these entries transition probabilities and note that a state may keep itself with probability $p_{ii}$.

Input: the story of the problem. Output: a list of states and a table of probabilities. To get the chance of being in state j after n steps starting from state i, multiply the matrix by itself n times and read entry (i, j) of the result (Theorem 11.1, p. 407). Matrix powers add up all the paths through the intermediate states for you. You now have the model; the next step answers questions about where it ends up.

Step 2: First-step analysis turns a walk into a few equations

First-step analysis asks one question: what can happen on the first move, and what is the answer from where I land? Take a symmetric walk on the squares 0, 1, 2, 3 that moves up or down with probability one half and stops at 0 or 3. Let h(i) be the chance of reaching 3 from square i. Then h(1) = ½h(0) + ½h(2) and h(2) = ½h(1) + ½h(3).

The boundary conditions are the part people forget: h(0) = 0 because the walk has stopped at 0, and h(3) = 1 because it has stopped at 3. For an expected time k(i) the equation gains a one for the step you just took, k(1) = 1 + ½k(0) + ½k(2), with k(0) = k(3) = 0. Weber's notes (Example 3.2) solve these and get h(1) = 1/3, h(2) = 2/3 and k(1) = k(2) = 2.¹

A state you cannot leave is an absorbing state: its self-transition probability is 1 (Grinstead and Snell, Chapter 11). For chains with absorbing states, the fundamental matrix $N=(I-Q{)}^{-1}$ gives expected visits (Definition 11.3), $t=Nc$ gives expected steps to absorption (Theorem 11.5) and $B=N·R$ gives absorption probabilities (Theorem 11.6). Here Q holds the moves among the non-absorbing states, R the moves into the absorbing ones and c is a column of ones. The equations are the same ones in matrix form.

Step 3: Gambler's ruin has a closed form

Gambler's ruin is the walk where a player with stake i wins one unit with probability p and loses one with probability q, and plays until the stake reaches 0 or a target N. In a fair game (p = q = ½) the chance of reaching N is i/N, the chance of ruin is 1 − i/N, and the expected duration is i(N − i) (Weber, Example 3.3; Grinstead and Snell, p. 487). The ruin probability is linear in the starting stake.

If the game is unfair, let $r=q/p$. The chance of reaching N becomes $\frac{1-r^i}{1-r^N}$ (Yurchenko-Tytarenko, lecture 10). The formula changes form at p = q because r equals 1 and the geometric sum collapses into a straight line.

The trap is the opponent. If the other side has unlimited wealth and p is at most one half, ruin has probability 1, even in a fair game; Weber (Example 3.5) puts it as "even if you find a fair casino you are certain to end up broke". If p exceeds one half, the ruin probability is $r^i$.

Step 4: The long run is a stationary distribution

A stationary distribution $\pi$ solves $\pi P=\pi$ with the entries of $\pi$ adding up to 1 (Yurchenko-Tytarenko, slide 29). It is a left eigenvector of P for eigenvalue 1, scaled to sum to 1. It answers "what share of time does the chain spend in each state in the long run?"

An ergodic chain is one that is irreducible (every state can reach every other), positive recurrent and aperiodic. Textbooks differ: Grinstead and Snell call an irreducible chain ergodic and an aperiodic one regular; here ergodic means irreducible, positive recurrent and aperiodic. For a regular chain, $P^n$ converges to a matrix whose rows all equal one vector, whatever the start (Grinstead and Snell, Theorem 11.7), and an ergodic chain has a unique strictly positive stationary vector (Theorem 11.10).

In the Land of Oz weather example the three weather types settle at .4, .2 and .4 whatever the start (p. 408). Without ergodicity, a periodic chain can have $\pi$ while $P^n$ never settles, and a chain with several recurrent classes can have several stationary vectors.

1 · States and matrix2 · First-step equations3 · Ruin formulas4 · Stationary vectorReplay

Step-by-step description

1. List the states and the transition probabilities.
2. Condition on the first move; set the boundaries.
3. Fair game is a line; unfair uses q over p.
4. Solve pi P = pi for the long run.

• A Markov chain is fixed by its states, a transition matrix and a starting distribution.
• First-step analysis conditions on the first move and gives linear equations.
• Gambler's ruin has a closed form for a fair and an unfair game.
• A stationary distribution is left unchanged by one step of the chain.

A Markov chain is fixed by its states, a transition matrix and a starting distribution. First-step analysis conditions on the first move and gives linear equations. Gambler's ruin has a closed form for a fair and an unfair game. A stationary distribution is left unchanged by one step of the chain.

Worked example

Start with the drunkard's walk: corners 0 to 4, absorbing at 0 and 4, one half each way. From Grinstead and Snell (Examples 11.13 to 11.15), N = [[3/2, 1, 1/2], [1, 2, 1], [1/2, 1, 3/2]], so the expected steps to absorption are t = (3, 4, 3), and from corner 2 the expected visits to corners 1, 2 and 3 are 1, 2 and 1. The script recomputes this and gets the absorption probabilities B: from corner 1 the chance of ending at 0 is 3/4 and at 4 is 1/4, and from corner 2 it is 1/2 each.¹

Now a fair gambler with stake 3 and target 10. The chance of reaching 10 is 3/10 = 0.3 and the expected duration is 3 × 7 = 21 plays.¹ The same method gives a classic: a symmetric walk from 0 needs on average $N^2$ steps to hit $+N$ or $-N$. Shift the walk by N, so it starts at N between barriers 0 and 2N, and the duration formula gives $N\times N$; for N = 10 that is 100 steps.¹

For an unfair coin with p = 0.6, so q/p = 2/3, start 5 and target 15, the chance of reaching the target is about 0.8703 (Yurchenko-Tytarenko, slide 12 gives ≈ 0.87). For start 10 and target 30 the script gives 0.9827, which corrects a typo on that slide (it prints a denominator of $(2/3{)}^{15}$ where $(2/3{)}^{30}$ is needed); the slide's ≈ 0.98 is right only by rounding.¹

The pattern problems are Markov chains on progress states. For two heads in a row the states are "no progress", "one head" and "done". The equations are $t_0=1+\frac{1}{2}{t}_1+\frac{1}{2}{t}_0$ and $t_1=1+\frac{1}{2}·0+\frac{1}{2}{t}_0$, which give $t_0=6$; for a head then a tail, a miss after a head keeps you in "one head", which gives 4.¹ The stationary row uses an illustrative two-state matrix with rows (0.9, 0.1) and (0.5, 0.5); solving $\pi P=\pi$ gives (5/6, 1/6), and the rows of $P^n$ approach it.¹

At stake 5 of 10 the fair game ruins with probability 0.5 and a game with win probability 0.6 with 0.1164.¹ The same script simulates fair games with stake 3 and target 10 and checks the estimates agree with 0.3 and 21 within sampling error.

Text description of the diagram

• Fair-game ruin probability is linear in the starting stake.
• At stake 5 of 10 the fair game ruins with probability 0.5 and a game with win probability 0.6 with 0.1164.

Trade-offs and edge cases

Pick the tool from the wording of the question. "Chance of hitting a barrier first" is a probability version of first-step analysis whose unknown is a probability. "Expected time to finish" uses the same equations with a one added for each step. "Long-run share of time" is a stationary distribution. "Will it ever come back?" is a return question.

Text description of the diagram

• Chance-of-hitting questions use first-step equations whose unknown is a probability.
• Expected-time questions use the same equations with one added for each step.

Chance-of-hitting questions use first-step equations whose unknown is a probability. Expected-time questions use the same equations with one added for each step.

Edge cases the textbook answer hides:

• Return to the start. The symmetric walk on the integers returns to the origin with probability 1 and is called recurrent; a biased walk is transient (Weber, Example 6.1). The probability of being at the origin at time 2m is $\frac{(2m)!}{m!m!2^{2m}}$, and at odd times it is 0 (Grinstead and Snell, Theorem 12.1); this is not the first-return probability. The walk is recurrent exactly when the sum of these origin probabilities over all times diverges. A mean displacement of zero does not mean the walk stays near zero or never returns.
• Periodic chains. A walk that can return only in even numbers of steps has a stationary distribution but $P^n$ does not converge.
• Several recurrent classes. Solving $\pi P=\pi$ then gives more than one answer, so state the class you mean.
• Higher dimensions. By Pólya's theorem the simple symmetric walk is recurrent in one and two dimensions and transient in three; Weber, Example 6.2 shows the two-dimensional case by comparing the return probabilities with a harmonic series.
• Prices. Using a random walk as a model of asset prices is a modelling choice, and this page makes no claim about how well it fits real markets. Practice with a pricing-style probability problem is in the make a market interview question page.

How to answer it in an interview

The spoken structure: name the states, write the first-step equation, state the boundaries, give the result and say when the formula changes.

Common mistakes

• "Markov means the future is independent of the past." (wrong) It is independent of the past given the present. (right) "The next step depends only on the current state."
• "A fair game cannot ruin me." (wrong) Against an infinitely rich house, ruin has probability 1 even in a fair game. (right) "With finite barriers the ruin probability is 1 − i/N; with an unlimited opponent it is 1."
• "I will use the unfair-game formula for any p." (wrong) At p = q the ratio q/p is 1 and the formula becomes 0/0, which is indeterminate. (right) "Use i/N for the fair case and the ratio formula otherwise."
• "The stationary distribution is where every chain ends up." (wrong) It needs ergodicity; a periodic chain may never settle. (right) "I check irreducible, positive recurrent and aperiodic before I claim a limit."
• "A fair walk drifts away, so it never comes back." (wrong) The mean displacement is 0 and the walk returns with probability 1 in one dimension. (right) "It returns, and only at even times."

Follow-up questions

What is the Markov property?

The Markov property says the next state depends only on the current state. Given the present, the earlier path adds no information about the next step.

Is a random walk a Markov chain?

Yes. A simple random walk on the integers moves up with probability p and down with probability q from wherever it stands, so its next position depends only on the current one (Weber, Example 6.1). The statistics for quant interviews guide covers the probability behind this.

What is the gambler's ruin problem?

Gambler's ruin is the question of whether a player who wins or loses one unit per play reaches a target before hitting zero. The fair-game answer is i/N and the biased answer uses the ratio q/p, as in Step 3.

How do you find the stationary distribution of a Markov chain?

Solve $\pi P=\pi$ together with the condition that the entries of $\pi$ sum to 1. Check that the chain is ergodic, otherwise the solution may not be unique or may not be the long-run limit.

How many coin flips does it take to get two heads in a row?

Six flips on average. Model the progress states, write the first-step equations and solve them, as in the worked example; a head followed by a tail takes 4 on average.¹

Does a fair random walk always return to where it started?

In one dimension the symmetric walk returns with probability 1, so a return is certain. The mean time to return is infinite, which is called null recurrence, and that is the usual next question. Returns also happen only at even times. For wider coverage of the technical rounds, see the quantitative finance interview guide.

Sources

1. Introduction to Probability, Chapters 11 and 12 (Markov chains, random walks) — Grinstead and Snell, The CHANCE Project, Dartmouth / AMS, 25 Oct 2026
2. Markov Chains (Part IB lecture notes) — R. R. Weber, Statistical Laboratory, University of Cambridge, 26 Oct 2026
3. Lecture 10: Gambler's ruin problem. Mean time in transient states (STK2130) — Anton Yurchenko-Tytarenko, University of Oslo, 18 Feb 2022