Statistical simulation

Markov Chain Simulator

Define a Markov chain through its transition matrix, choose an initial state, and watch how the state distribution converges to the stationary distribution.

Preset

Transition matrix P

Each row represents the current state; each column, the next state. Each row must sum to 1.

Select a preset or configure the matrix and click “Simulate”

State evolution (cumulative proportion)

Final distribution vs stationary distribution

Stationary distribution:

Empirical distribution (fraction of time):

Maximum difference |π − empirical|:

Interpretation:

What is a Markov chain?

A Markov chain is a discrete-time stochastic process \(\{X_0, X_1, X_2, \ldots\}\) that takes values in a finite set of states and satisfies the Markov property, or "memorylessness":

$$P(X_{n+1} = j \mid X_0, X_1, \ldots, X_n) = P(X_{n+1} = j \mid X_n) = p_{ij}$$

The probability of moving to the next state depends only on the present state, not on how it was reached. This greatly simplifies the mathematical analysis without sacrificing realism in many applications.

The complete behavior of the chain is fully specified by the transition matrix \(P\), where the element \(p_{ij}\) is the probability of moving from state \(i\) to state \(j\) in one step:

$$P = \begin{pmatrix} p_{11} & p_{12} & \cdots & p_{1n} \\ p_{21} & p_{22} & \cdots & p_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ p_{n1} & p_{n2} & \cdots & p_{nn} \end{pmatrix}, \quad \sum_{j=1}^{n} p_{ij} = 1 \text{ for every } i$$

Each row of the transition matrix is a probability distribution: the values are non-negative and sum to 1. This makes \(P\) a stochastic matrix (or Markov matrix).

Stationary distribution

A stationary distribution (or equilibrium distribution) is a probability vector \(\pi = (\pi_1, \pi_2, \ldots, \pi_n)\) such that:

$$\pi P = \pi \quad \text{with} \quad \sum_{i=1}^{n} \pi_i = 1, \quad \pi_i \geq 0$$

Intuitively, if the chain is in the stationary distribution at time \(n\), it will remain in that distribution forever. In practice, it represents the long-run fraction of time the chain spends in each state.

Existence and uniqueness conditions

  • Irreducibility: every state is reachable from every other state (the chain is a strongly connected graph). This guarantees that a unique stationary distribution exists.
  • Aperiodicity: no state has a period greater than 1. Together with irreducibility, this guarantees the convergence of the state distribution toward \(\pi\) regardless of the initial state.
  • A chain that is both irreducible and aperiodic is called ergodic. For ergodic chains, \(\pi\) is the unique stationary distribution and the chain converges to it.

Absorbing state: the Customer / Churn preset

In the Customer preset, the "Churn" state is an absorbing state: \(p_{\text{churn}, \text{churn}} = 1\). Once a customer leaves, they don't come back. This makes the chain non-ergodic: eventually every customer ends up in Churn. The stationary distribution assigns probability 1 to that state and 0 to the rest.

Real-world applications

  • PageRank (Google): the web is modeled as a Markov chain in which the states are pages and the transitions are hyperlinks. The stationary distribution determines the relevance of each page.
  • Weather models: states such as Sunny, Cloudy and Rainy with transition probabilities fitted to historical data.
  • Customer lifecycle: Active → Dormant → Churn. Lets you compute the expected value of a customer and design retention strategies.
  • Text generation: n-gram models are Markov chains in which the state is the sequence of the last \(n\) words and the transition picks the next one.
  • MCMC in Bayesian statistics: the Metropolis-Hastings and Gibbs sampling algorithms build Markov chains whose stationary distribution is the posterior of interest.
  • Population genetics: the Wright-Fisher model describes how allele frequencies change in a finite population through a Markov chain.
  • Queueing theory: Markov chains model the number of customers in an M/M/1 or M/M/k queue, allowing the computation of waiting times and service rates.

Frequently asked questions

How many steps are needed to reach equilibrium?

It depends on the chain's mixing time, which is related to the second-largest eigenvalue (in absolute value) of the transition matrix, \(|\lambda_2|\). The closer \(|\lambda_2|\) is to 1, the slower the convergence: the chain "remembers" its initial state for a long time. Formally, the distance between the distribution at step \(t\) and the stationary distribution decreases approximately as \(|\lambda_2|^t\). For the Weather preset, mixing is relatively fast; for chains with nearly absorbing states or low connectivity, it can take thousands of steps.

Does the chain always converge to the same distribution regardless of the initial state?

Yes, as long as the chain is ergodic (irreducible and aperiodic). In that case, the Markov Ergodic Theorem guarantees that the distribution at step \(n\) converges to the unique stationary distribution \(\pi\) for any initial state. The Weather preset is ergodic. On the other hand, if the chain has several absorbing states or is not irreducible, the limiting distribution can depend on the starting state.

What happens with the Customer / Churn preset?

The "Churn" state is absorbing: \(p_{\text{Churn},\text{Churn}} = 1\) and the other \(p_{\text{Churn},j} = 0\). Once in Churn, there's no way out. This means the chain is not irreducible, and the only stationary distribution is \(\pi_{\text{Churn}} = 1\), \(\pi_{\text{Active}} = \pi_{\text{Dormant}} = 0\). If you run the simulation for many steps, you'll see the proportion of time spent in Churn keep growing toward 1. This is the basis of time-to-absorption analysis, a key metric in customer management.

How is the stationary distribution computed numerically?

The simulator uses power iteration: it starts from an initial probability vector (the uniform distribution) and repeatedly multiplies it by the matrix \(P\) until the change between iterations is smaller than \(10^{-9}\). This process converges to the stationary distribution (if it exists and is unique) within a few thousand iterations. Analytically, \(\pi\) is the left eigenvector of \(P\) associated with eigenvalue 1.

Why does the simulator show horizontal reference lines in the evolution chart?

The dashed horizontal lines mark the theoretical value of the stationary distribution \(\pi_i\) for each state \(i\). As the simulation progresses, the solid lines (cumulative proportion of time spent in each state) converge toward those reference values. This convergence is the empirical manifestation of the ergodic theorem.

Related tools

Probability distributions

Continuous-time Markov chains are related to the exponential distribution (sojourn times in each state). Also explore the Poisson distribution and other discrete distributions.

Other simulations

Complement this with the central limit theorem simulator, the confidence interval simulator and the Poisson process simulator.

Hypothesis tests

Once you're familiar with probabilistic models, apply them in the hypothesis tests available on ProbLab.