Markov chains in the Data Science interview

Why Markov chains show up on DS loops

You will not get hired at Stripe, Netflix or DoorDash because you can recite the Chapman-Kolmogorov equation. You will get hired because when the interviewer says "users move between three engagement tiers and we want the long-run share of power users," you can immediately reach for a transition matrix and a stationary distribution without panic. That is the actual job — pattern-matching a vague product question to a tool that already exists.

Markov chains sit underneath an unreasonable amount of applied ML: PageRank, HMM-based ASR baselines, MCMC samplers in PyMC and Stan, reinforcement learning state transitions, churn and lifecycle models, and most of the random-walk literature on graphs. Senior DS candidates at OpenAI, Anthropic and Snowflake routinely get probed on at least one of these — usually MCMC convergence or stationary distributions — because they reveal whether you understand sampling beyond train_test_split.

The Markov property

The Markov property says the future depends only on the current state, not the entire history. Formally:

P(x_{t+1} | x_t, x_{t-1}, ..., x_1) = P(x_{t+1} | x_t)

This is the memoryless assumption. It does not mean history is irrelevant in reality — it means we have engineered the state so that everything relevant is already encoded in x_t. A user's "engagement tier today" is Markov if it summarizes everything we need; it stops being Markov if churn next month actually depends on what they did three months ago and that signal is not in the current state.

This distinction comes up in product interviews way more than people expect — interviewers love to ask "is this process actually Markov?" as a trap.

Transition matrix and n-step dynamics

A transition matrix P has entries P[i, j] equal to the probability of moving from state i to state j in one step. Rows must sum to 1.

import numpy as np

# States: A (casual), B (engaged), C (power)
P = np.array([
    [0.70, 0.20, 0.10],  # from A
    [0.30, 0.50, 0.20],  # from B
    [0.10, 0.40, 0.50],  # from C
])

assert np.allclose(P.sum(axis=1), 1.0)

The distribution after n steps is π_n = π_0 · P^n. This is the workhorse identity. If a recruiter asks you "starting from 100% casual users, what fraction are power users after 6 months?" — that is literally π_0 @ np.linalg.matrix_power(P, 6).

Stationary distribution

The stationary distribution π satisfies π · P = π. Interpretation: if you start the chain from π, you stay in π forever. For ergodic chains (irreducible + aperiodic), π is unique and any starting distribution converges to it.

eigenvalues, eigenvectors = np.linalg.eig(P.T)
idx = np.argmin(np.abs(eigenvalues - 1))
stationary = np.real(eigenvectors[:, idx])
stationary = stationary / stationary.sum()
print(stationary)  # e.g. [0.40, 0.35, 0.25]

PageRank is exactly this: build the web graph as a Markov chain, add teleportation for ergodicity, compute the stationary distribution — that vector is the rank. The same machinery powers churn-equilibrium models ("what is the long-run share of paid users assuming current transition rates hold?") and inventory rotation analyses.

Hidden Markov Models

In an HMM the state is not observed directly. You see emissions y_t that depend on the latent state x_t, and x_t itself follows a Markov chain.

Hidden: x_1 → x_2 → x_3 → ...   (Markov chain)
Visible: y_1   y_2   y_3   ...   (each y_t depends on x_t)

Three canonical algorithms make HMMs tractable:

• Forward-backward. Computes P(x_t | y_{1:T}) for every t. Used for smoothing — what was the user's likely state at time t given the full session?
• Viterbi. Returns the single most likely state sequence given observations. Used in decoding — POS tagging, gene segmentation, simple speech recognition baselines.
• Baum-Welch. An EM algorithm that estimates transition and emission parameters from unlabeled sequences.

Applied uses today: bioinformatics (gene finding, protein motifs), NLP POS tagging as a baseline, session segmentation in product analytics, and pre-transformer speech recognition. Modern ASR is neural, but HMM intuition still shows up in alignment layers.

Where T is sequence length, K is number of hidden states, I is EM iterations.

MCMC for Bayesian inference

Markov Chain Monte Carlo is the trick that makes Bayesian inference work when the posterior is intractable. You construct a Markov chain whose stationary distribution equals the target posterior, run it for a while, and treat the samples as approximate draws from that posterior.

Four samplers worth knowing by name:

• Metropolis-Hastings. Propose a move, accept with probability min(1, ratio). Universal but slow in high dimensions.
• Gibbs sampling. Update one coordinate at a time from its conditional. Cheap when conditionals are tractable.
• HMC (Hamiltonian Monte Carlo). Uses gradient information to propose long-range moves. Vastly better in continuous high-dim spaces.
• NUTS (No-U-Turn Sampler). Adaptive HMC that tunes trajectory length. Default in PyMC and Stan.

import pymc as pm

with pm.Model():
    mu = pm.Normal("mu", 0, 10)
    sigma = pm.HalfNormal("sigma", 5)
    pm.Normal("y", mu, sigma, observed=data)
    # NUTS by default
    trace = pm.sample(2000, tune=1000, chains=4)

Convergence diagnostics interviewers love: R-hat below 1.01, effective sample size above 400 per chain, no divergences, and stable trace plots across chains. If R-hat is 1.05 or higher, your chains have not mixed and you cannot trust the posterior summaries.

Common pitfalls

A frequent trap is assuming the chain is Markov without checking. People wave the Markov property at any sequence problem, but if next-month churn depends on a feature absent from the current state, you have an order-2 or higher process and your stationary calculations are nonsense. The fix is to augment the state — include lagged features, session counts, or whatever leaked memory you missed — and re-validate by comparing predicted versus empirical transition counts on a holdout window.

Another pitfall is forgetting ergodicity conditions before computing a stationary distribution. Reducible chains have multiple stationary distributions; periodic chains never converge from arbitrary starts. In product data this shows up as states with zero outflow (a "deleted account" absorbing state) or strict cycles. The diagnostic is to look for absorbing states or strongly connected components in the transition graph before quoting any long-run share. If you have absorbing states, model time-to-absorption instead of stationarity.

A subtler trap is comparing observed steady-state shares with the stationary distribution and concluding "the system is in equilibrium". Real product systems are non-stationary — transition probabilities drift with seasonality, launches and pricing changes. The fix is to recompute P on a rolling window (monthly or quarterly) and treat any stationary calculation as conditional on the snapshot. Quoting an annual stationary distribution from a 2-week sample is a senior-level red flag.

MCMC chains that look converged but are not is the canonical applied-Bayesian mistake. A single chain can produce smooth trace plots while being stuck in one mode of a multimodal posterior. The fix is always run at least 4 chains from different inits, check R-hat per parameter, and inspect divergences in NUTS — divergences mean the geometry has regions HMC cannot traverse, often indicating reparameterization is needed.

Finally, candidates routinely confuse Markov chains with Markov decision processes. A plain Markov chain has transition probabilities; an MDP adds actions and rewards. Reinforcement learning lives in MDP-land, not chain-land. If an interviewer asks about policy iteration, you are in MDP territory and need value functions, not eigenvectors.

Related reading

• Bayesian methods in the Data Science interview
• Bayes theorem explained simply
• Bayesian A/B testing
• Time series feature engineering for DS
• Bayesian optimization interview

If you want to drill DS interview questions like this every day, NAILDD is launching with 1,500+ problems across exactly this pattern.

FAQ

Is a Markov chain the same as a Markov decision process?

No. A Markov chain has only transition probabilities between states. A Markov decision process adds an action space and a reward function, so the transition probability becomes P(x_{t+1} | x_t, a_t) and the goal is to find a policy mapping states to actions. Reinforcement learning algorithms — Q-learning, policy gradients, actor-critic — all live in MDP-land. If the interviewer mentions rewards or policies, switch frames immediately.

When can I safely compute a stationary distribution?

When the chain is irreducible (every state reachable from every other state) and aperiodic (no strict cycles). In practice that means no absorbing states and at least one self-loop or non-cyclical structure. If you have an absorbing "churned forever" state, you do not have a stationary distribution in the classical sense — you have an absorbing chain, and the right tool is expected time to absorption.

What is mixing time and why should I care?

Mixing time is roughly how many steps the chain needs before the distribution is close to stationary regardless of the start. For product applications it tells you how quickly forecasts converge: if mixing time is 6 months but your business plans on a quarterly horizon, the stationary distribution is a misleading anchor. Spectral gap (the difference between the largest and second-largest eigenvalue of P) controls mixing — large gap means fast mixing.

How do I diagnose a bad MCMC run?

Look at R-hat per parameter (target below 1.01), effective sample size (target at least 400 per chain), divergence counts in NUTS, and trace plots across multiple chains. If chains look like flat lines that never explore — increase target acceptance or reparameterize. If they bounce wildly — reduce step size or use a non-centered parameterization. Multimodal posteriors often need explicit tempered methods rather than vanilla NUTS.

Are HMMs still useful given transformers?

For headline tasks like ASR and machine translation, no — transformer models dominate. But HMMs remain useful where you have short sequences, limited data, and need interpretable latent states: user journey segmentation, alignment in bioinformatics, simple anomaly detection on telemetry. The training is cheap, the model is transparent, and Viterbi decoding gives you a clean state sequence you can ship to a PM without explaining attention heads.

Do I need to derive the Metropolis-Hastings acceptance ratio in an interview?

For most applied DS roles, no — you should be able to explain it in words and write the formula min(1, [π(x') q(x|x')] / [π(x) q(x'|x)]) if pushed. For research roles at Anthropic, OpenAI, or quant funds, expect to derive it and discuss detailed balance. The level of detail scales with how much the role touches probabilistic modeling versus production ML pipelines.