Markov Simulation: Simulate a Markov Chain and Compute Steady-State Probabilities
Interview Experience
Round 1 Coding
Problem
Given a Markov chain as a transition matrix (rows sum to 1), simulate N steps from a given starting state and estimate the steady-state distribution. Also implement exact power iteration to compute the true stationary distribution.
python
import random
def simulate_chain(transition: list[list[float]],
start_state: int, steps: int) -> list[float]:
**returns** empirical state visit frequencies
...
def stationary_distribution(transition: list[list[float]],
tol: float = 1e-8) -> list[float]:
# power iteration until convergence
...
Example
T = [
[0.9, 0.1],
[0.5, 0.5],
]
# Exact stationary: solve pi*T = pi; pi[0]+pi[1]=1
# -> pi = [0.833..., 0.166...]
stationary_distribution(T) -> [0.8333, 0.1667] # approx
simulate_chain(T, start_state=0, steps=10000)
# -> [~0.83, ~0.17] (empirical, will vary)
Follow-ups
- How do you detect whether a Markov chain has a unique stationary distribution (is it ergodic/irreducible/aperiodic)?
- How many steps does simulation typically need to converge? What influences the mixing time?
- How would you extend this to a continuous-time Markov chain using a rate matrix (generator matrix)?
- How would you visualize the chain as a directed graph with edge weights?
Full Details
Round 1 Coding
Problem
Given a Markov chain as a transition matrix (rows sum to 1), simulate N steps from a given starting state and estimate the steady-state distribution. Also implement exact power iteration to compute the true stationary distribution.
python
import random
def simulate_chain(transition: list[list[float]],
start_state: int, steps: int) -> list[float]:
**returns** empirical state visit frequencies
...
def stationary_distribution(transition: list[list[float]],
tol: float = 1e-8) -> list[float]:
# power iteration until convergence
...
Example
T = [
[0.9, 0.1],
[0.5, 0.5],
]
# Exact stationary: solve pi*T = pi; pi[0]+pi[1]=1
# -> pi = [0.833..., 0.166...]
stationary_distribution(T) -> [0.8333, 0.1667] # approx
simulate_chain(T, start_state=0, steps=10000)
# -> [~0.83, ~0.17] (empirical, will vary)
Follow-ups
- How do you detect whether a Markov chain has a unique stationary distribution (is it ergodic/irreducible/aperiodic)?
- How many steps does simulation typically need to converge? What influences the mixing time?
- How would you extend this to a continuous-time Markov chain using a rate matrix (generator matrix)?
- How would you visualize the chain as a directed graph with edge weights?
About This Question
This is a candidate experience report from a retool interview during the phone round.
It covers the following topics: Phone, Graph, Coding, Onsite, Matrix .