Markov Chain Interview Questions: Choosing States, Hitting Times, and Absorption

You flip a fair coin until two consecutive heads appear. “The pattern has probability one quarter, so the answer is four flips” sounds plausible. It is also wrong: the expected waiting time is six. The missing detail is that successive two-flip windows overlap, and the useful history changes after each flip.

Markov chain interview questions reward the ability to choose a state before choosing a formula. A good answer identifies what the future depends on, defines exactly when the experiment stops, and checks that the resulting equations describe that experiment. This guide develops those habits through coin patterns, capital boundaries, and a target that can become unreachable.

Evidence boundary: Definitions and absorption results below come from linked mathematical references. The worked exercises and answer-review suggestions are original preparation material. They are not candidate reports or predictions about a particular employer’s questions.

How do you choose a state that preserves the right history?

The Markov property says that the conditional distribution of the next state, given the past, depends only on the present state. It does not say that every variable someone calls a “state” satisfies that property. The distinction follows the definition in Maria Cameron’s Markov chain notes.

For a coin-pattern problem, “number of heads seen so far” usually loses the ordering information. “Number of flips elapsed” also fails to distinguish a sequence ending in H from one ending in T. For the target HH, a sufficient description is:

• 0: no trailing head that can begin the target;
• H: the last flip was a head, and the target is unfinished;
• Done: HH has appeared, so the experiment stops.

Two different histories can enter H: TH and TTH both leave exactly one useful trailing head. Their next-step behavior is identical. Conversely, HT and TH cannot share the same unfinished state: a head completes HH from TH but merely starts a new partial match from HT.

An interview explanation can therefore start with a concrete test: “If I merge these two histories, could the same next observation cause different progress toward the target?” If yes, the proposed state is too coarse. Keeping the entire history is sufficient but wasteful; the objective is a compact description that still predicts the future correctly.

State sufficiency also depends on assumptions. If the coin has a hidden regime that changes its bias, a suffix alone might not be Markov. If a transition probability changes with calendar time, specify a time-dependent chain or include the needed time information. Do not silently solve the independent, constant-bias problem when the prompt describes something else.

Why does HH take six flips while HT takes four?

Let E0 and EH be the expected additional flips before HH, starting in states 0 and H. Set the remaining time in Done to zero. Conditioning on the next fair flip gives:

E0 = 1 + 0.5 E0 + 0.5 EH
EH = 1 + 0.5 E0

The leading one counts the next flip, including the successful final flip. From H, another H finishes; a T loses the partial match and returns to 0. Rearranging the first equation gives E0 = 2 + EH. Substituting into the second gives EH = 4 and E0 = 6.

Now change only the target to HT. Keep 0, H, and Done, but update the transition from H: a T finishes, while another H leaves a useful trailing H. The equations become:

E0 = 1 + 0.5 E0 + 0.5 EH
EH = 1 + 0.5 EH

Here EH = 2 and E0 = 4. Both patterns have probability one quarter in a particular pair of independent flips. Their waiting times differ because the process searches overlapping windows, rather than testing independent two-flip blocks.

This comparison is useful when an interviewer asks you to repair an initial answer. Point to the transition you overlooked, redraw it, and solve the revised equations. Merely replacing four with six does not demonstrate that you understand the error.

If the probability of H is p, the HH equations become E0 = 1 + (1−p)E0 + pEH and EH = 1 + (1−p)E0. For p greater than zero, the solution is E0 = (1+p)/p². At p = 1, it gives two flips; as p approaches zero, the wait grows without bound. At p = 0, the target is unreachable, so do not substitute zero into a formula with a zero denominator.

How do overlapping patterns change the transition table?

For HTH, use the longest suffix of the observed sequence that is also a prefix of the target. The unfinished states are Empty, H, and HT. An H after H stays in H: the newest head can start a fresh HTH. Resetting to Empty would discard useful information.

Current state	Next flip H	Next flip T
Empty	H	Empty
H	H	HT
HT	Done	Empty
Done	Done	Done

The final row makes Done absorbing for this stopping-time calculation. It describes the stopped experiment, even though someone could physically keep flipping coins afterward.

Writing EEmpty, EH, and EHT for additional flips gives EEmpty = 1 + 0.5EEmpty + 0.5EH, EH = 1 + 0.5EH + 0.5EHT, and EHT = 1 + 0.5EEmpty. These solve to 10, 8, and 6, respectively. The starting answer is ten because the experiment begins with no useful suffix.

Check the model against the sequence HHTH. It progresses Empty → H → H → HT → Done. A model that resets after HH would miss the completed pattern at the fourth flip. This short counterexample tests state design more effectively than a large simulation with an unexplained average.

For a longer pattern, the same suffix rule gives a systematic construction. You can describe the principle without writing a full string-matching algorithm unless the prompt asks for implementation. The interview value lies in explaining how each transition preserves precisely the part of the past that can still contribute to a future match.

How do hitting probabilities differ from hitting times?

Consider capital moving by one unit up or down with equal probability. Stop at either 0 or 5. Starting with two units, what is the chance of reaching 5 first, and how many steps do you expect before either boundary?

These are two separate unknowns. Let hi be the probability of reaching 5 before 0. Let ti be the expected steps to either boundary. First-step conditioning gives:

h0 = 0, h5 = 1
hi = 0.5 h(i−1) + 0.5 h(i+1)

t0 = 0, t5 = 0
ti = 1 + 0.5 t(i−1) + 0.5 t(i+1)

The solutions are hi = i/5 and ti = i(5−i). From two units, the success probability is 0.4, while the mean time to a boundary is 6 steps. That six includes paths ending in failure at zero. It is not the mean time to reach five conditional on success.

Boundary conditions carry the question’s meaning. If the prompt asks about “time to success,” clarify whether failed paths count as infinite, are excluded by conditioning, or trigger a restart. Each interpretation produces a different model. Also distinguish hitting a state at time zero from returning after at least one transition; a chain starting at its target has zero first hitting time under the former convention.

A matrix entry in P raised to k gives the probability of being in a state after k steps. It does not generally give the probability of first arriving there at step k. Paths can visit, leave, and revisit the state. Making the target absorbing can turn endpoint probabilities into cumulative hitting probabilities for the modified chain, but you must explain that modification.

When can you use the absorbing-chain matrix formulas?

For a finite chain with transient states listed before absorbing states, write the transient-to-transient block as Q and the transient-to-absorbing block as R. Under the absorbing-chain conditions, the fundamental matrix N = (I−Q)⁻¹ counts expected visits to transient states. Its row sums give expected absorption times; NR gives absorption probabilities. These results are explained in Grinstead and Snell’s absorbing-chain chapter and Yen-Chi Chen’s discrete-time chain lecture.

For the capital example, the transient states are 1 through 4. Each interior row of Q has one-half probability on each neighboring transient state where that neighbor exists. The missing row mass goes to an absorbing endpoint through R. Q therefore need not have rows summing to one; the full transition matrix must.

In code, solve (I−Q)t = 1 rather than explicitly computing an inverse solely to obtain t. Explain your state ordering, check the equation residual, and ensure the computed times are nonnegative. For absorption probabilities, check values lie between zero and one and that probabilities across all absorbing outcomes sum to one under the model’s assumptions.

Before applying a formula, inspect the graph. Suppose Start moves to Success with probability one-half and to Trap with probability one-half, and Trap loops forever. The probability of hitting Success is one-half. The unconditional time to Success is infinite, because half the paths never arrive. Calling Trap “transient” and trying to invert the corresponding block is a modeling error; counting absorption in either Success or Trap answers a different question.

How should you discuss estimated transitions and validate an answer?

Given observed transitions, a straightforward estimate of Pij divides the count from i to j by the total observed departures from i. A row with no departures has no such estimate. Filling it with a self-loop declares the state absorbing; that is a modeling assumption, not a fact established by missing data.

Explain whether you will gather more observations, impose a domain constraint, or use an explicit smoothing model. Also ask whether the observations come from one stable process. Pooling transitions across different operating regimes can hide dependence that your state definition should represent.

For a finished answer, review three layers: the state distinguishes relevant histories; each transition matches a possible observation; the numerical result satisfies both the equations and the boundaries. Simulation can reveal implementation mistakes, but an apparently stable average cannot prove the state model is correct or establish a finite expectation.

Five Markov chain practice questions

The descriptions below are preparation suggestions, not claims about current employer frequency or assessment content.

Practice question	What to practice
Compute multi-step Markov probabilities and estimate transitions	Separate matrix powers from estimated one-step transition rows.
Derive expectation for two consecutive heads	Define partial progress and count the final successful flip.
Compute gambler’s ruin probabilities and hitting times	Give success probability and time to either boundary separately.
Compute Random Walk Hitting and Return Probabilities	State the stopping event and distinguish hitting from returning.
Compute and estimate Markov transition probabilities	Explain what a transition estimate can and cannot establish.

Start with the coin-pattern question, derive the answer aloud, and then change one transition. Once you can explain why the answer changes, move to the broader Data Scientist question collection to connect probability reasoning with modeling decisions.

Sources and further reading

• Maria Cameron, University of Maryland: Markov chain lecture notes
• Yen-Chi Chen, University of Washington: Discrete-time Markov chains, lecture 4
• Grinstead and Snell: Absorbing Markov chains