Markov Chain Steady-State & Transition Calculator

Foundational Theory of Discrete-Time Markov Chains (DTMC)

A discrete-time Markov chain is a mathematical sequence of random variables ${X_0, X_1, X_2, dots, X_n, dots}$ taking values in a countable or finite discrete state space $mathcal{S} = {s_1, s_2, dots, s_K}$. Formulated in 1906 by Russian mathematician Andrey Andreyevich Markov to prove that independence was not a necessary prerequisite for the Weak Law of Large Numbers, Markov chains form the bedrock of modern queuing theory, statistical mechanics, algorithmic PageRank search, speech recognition, and quantitative finance.

The defining hallmark of any Markovian process is the Markov Property (the principle of memorylessness). Formally, conditional on the present state $X_n$, future evolution $X_{n+1}$ is statistically independent of past historical trajectories ${X_0, X_1, dots, X_{n-1}}$:

For a time-homogeneous chain, the one-step transition probabilities $P_{ij}$ are constant across time, giving rise to the $K imes K$ stochastic transition probability matrix $mathbf{P}$:

Because every transition probability must be non-negative and the chain must transition to some state in $mathcal{S}$ at step $n+1$, $mathbf{P}$ satisfies the Row-Stochastic Axioms:

1. $P_{ij} ge 0 quad orall i, j in mathcal{S}$
2. $sum_{j=1}^K P_{ij} = 1 quad orall i in mathcal{S} iff mathbf{P} mathbf{1} = mathbf{1}$

The Chapman-Kolmogorov Equations and n-Step Transitions

The probability of transitioning from state $i$ to state $j$ in exactly $n$ discrete time steps is denoted $P_{ij}^{(n)} = mathbb{P}(X_n = j mid X_0 = i)$. The fundamental Chapman-Kolmogorov theorem states that for any intermediate integer $m$ ($0 < m < n$):

In matrix notation, this reveals the remarkable algebraic simplicity of Markov chains: the $n$-step transition probability matrix $mathbf{P}^{(n)}$ is simply the $n$-th matrix power of the single-step transition matrix:

Given an initial state probability distribution vector $mathbf{p}^{(0)} = [mathbb{P}(X_0 = s_1), dots, mathbb{P}(X_0 = s_K)]$, the state probability distribution at time $n$ is: $$mathbf{p}^{(n)} = mathbf{p}^{(0)} mathbf{P}^n$$

Stationary Distributions and the Perron-Frobenius Theorem

A probability distribution row vector $oldsymbol{pi} = [pi_1, pi_2, dots, pi_K]$ is defined as a stationary distribution (or steady-state equilibrium) if it is invariant under the transition operator:

Notice that $oldsymbol{pi} mathbf{P} = oldsymbol{pi}$ is equivalent to saying that $oldsymbol{pi}$ is a normalized left-eigenvector of $mathbf{P}$ associated with the eigenvalue $lambda = 1$. By the Perron-Frobenius Theorem for non-negative matrices:

• The spectral radius $ ho(mathbf{P}) = 1$. The eigenvalue of largest absolute magnitude is always $lambda_1 = 1$.
• If the chain is irreducible (every state communicates with every other state, meaning $P_{ij}^{(n)} > 0$ for some $n$) and aperiodic (the greatest common divisor of return times to any state is 1), the chain is ergodic.
• For any ergodic chain, there exists a strictly unique positive stationary vector $oldsymbol{pi} > 0$.
• Regardless of the initial distribution $mathbf{p}^{(0)}$, the chain converges asymptotically to the steady-state: $$lim_{n o infty} mathbf{P}^n = egin{pmatrix} oldsymbol{pi} oldsymbol{pi} dots oldsymbol{pi} end{pmatrix} = mathbf{1} oldsymbol{pi}$$ Every row of $mathbf{P}^infty$ becomes identical to $oldsymbol{pi}$!

Mean Recurrence Time and Kac's Theorem

For any recurrent state $i$, let $T_i = min{n ge 1 mid X_n = i ext{ given } X_0 = i}$ be the first return time to state $i$. By Kac's Lemma, the mean recurrence time (expected number of steps between successive visits to state $i$) is simply the reciprocal of its stationary probability:

If $pi_i = 0.20$, the system visits state $i$ on average once every $1 / 0.20 = 5$ steps.

Absorbing Markov Chains and the Fundamental Matrix

A state $k$ is called absorbing if it is impossible to leave once entered: $P_{kk} = 1$ and $P_{kj} = 0$ for $j eq k$. Non-absorbing states are termed transient.

Reordering states into $r$ absorbing states and $t$ transient states partitions $mathbf{P}$ into canonical block form:

where $mathbf{Q}$ ($t imes t$) governs transitions among transient states, and $mathbf{R}$ ($t imes r$) governs transitions from transient to absorbing states.

1. The Fundamental Matrix ($mathbf{N}$): $$mathbf{N} = (mathbf{I}_t - mathbf{Q})^{-1} = mathbf{I} + mathbf{Q} + mathbf{Q}^2 + mathbf{Q}^3 + cdots$$ Entry $N_{ij}$ represents the expected number of times the process visits transient state $j$ before being absorbed, starting from transient state $i$.
2. Time to Absorption ($mathbf{t}$): $$mathbf{t} = mathbf{N} mathbf{1}_t$$ Entry $t_i$ is the expected total number of steps before absorption starting from transient state $i$.
3. Absorption Probabilities ($mathbf{B}$): $$mathbf{B} = mathbf{N} mathbf{R}$$ Entry $B_{ik}$ is the exact probability that the chain eventually gets absorbed by absorbing state $k$, starting from transient state $i$.

Step-by-Step Worked Numerical Examples

Example 1: 3-State Land of Oz Weather Cycle

States: $s_1 = ext{Rainy (R)}$, $s_2 = ext{Nice (N)}$, $s_3 = ext{Snow (S)}$.
The transition probability matrix is: $$mathbf{P} = egin{pmatrix} 0.5 & 0.25 & 0.25 0.5 & 0 & 0.5 0.25 & 0.25 & 0.5 end{pmatrix}$$

Step 1: Set up the linear stationary system $oldsymbol{pi} mathbf{P} = oldsymbol{pi}$:

Step 2: Solve algebraically:

Step 3: Mean Recurrence Times:

Example 2: Gambler's Ruin as an Absorbing Chain

A gambler starts with $$2$ and plays a fair game ($mathbb{P}( ext{Win}) = 0.5$, $mathbb{P}( ext{Lose}) = 0.5$), stopping if they reach $$0$ (bankrupt) or $$4$ (goal).
State space: $mathcal{S} = {0, 1, 2, 3, 4}$, where states $0$ and $4$ are absorbing.
Transient states are ${1, 2, 3}$. The transient matrix $mathbf{Q}$ is: $$mathbf{Q} = egin{pmatrix} 0 & 0.5 & 0 0.5 & 0 & 0.5 0 & 0.5 & 0 end{pmatrix}$$ $$mathbf{I} - mathbf{Q} = egin{pmatrix} 1 & -0.5 & 0 -0.5 & 1 & -0.5 0 & -0.5 & 1 end{pmatrix}$$ Inverting $mathbf{I} - mathbf{Q}$ yields the Fundamental Matrix: $$mathbf{N} = (mathbf{I} - mathbf{Q})^{-1} = egin{pmatrix} 1.5 & 1.0 & 0.5 1.0 & 2.0 & 1.0 0.5 & 1.0 & 1.5 end{pmatrix}$$ Expected time to ruin/victory starting with $$2$ (Row 2): $$t_2 = 1.0 + 2.0 + 1.0 = 4.0 ext{ games}$$ Probability of winning $$4$ starting with $$2$: $B_{2, 4} = 0.50$ (50%).

Comparative Analysis of Markovian Frameworks

Markov Theory FAQs