Ferkans — Interactive Telecom Tutor

Long-Run Behavior

The central question of Markov chain theory: if we run the chain for a very long time, does the distribution of $X_n$ settle down to a limit, independent of where the chain started? The answer is yes, under the right conditions, and the limiting distribution is the stationary distribution $\boldsymbol{\pi}$ . This distribution governs the long-run fraction of time spent in each state and is the key to computing steady-state performance metrics in communications systems.

Definition:
Stationary (Invariant) Distribution

A probability distribution $\boldsymbol{\pi} = (\pi_1, \pi_2, \ldots)$ on the state space $\mathcal{S}$ is a stationary distribution (or invariant distribution) for the DTMC with transition matrix $\mathbf{P}$ if

$\boldsymbol{\pi} = \boldsymbol{\pi} \mathbf{P},$

i.e., $\pi_j = \sum_{i \in \mathcal{S}} \pi_i \, p_{ij}$ for all $j \in \mathcal{S}$ , with $\pi_j \geq 0$ and $\sum_j \pi_j = 1$ .

If $X_0 \sim \boldsymbol{\pi}$ , then $X_n \sim \boldsymbol{\pi}$ for all $n$ : the distribution does not change over time.

The equation $\boldsymbol{\pi} = \boldsymbol{\pi} \mathbf{P}$ says that $\boldsymbol{\pi}$ is a left eigenvector of $\mathbf{P}$ for eigenvalue 1. Since $\mathbf{P}$ is stochastic, eigenvalue 1 always exists (the all-ones vector is a right eigenvector). The question is whether a non-negative left eigenvector with entries summing to 1 exists and is unique.

,

Stationary distribution

A probability vector $\boldsymbol{\pi}$ satisfying $\boldsymbol{\pi} = \boldsymbol{\pi}\mathbf{P}$ . If the chain starts in this distribution, it stays in it forever.

Theorem: Existence and Uniqueness of the Stationary Distribution

Let $\{X_n\}$ be an irreducible DTMC on a countable state space $\mathcal{S}$ .

If the chain is positive recurrent (i.e., the expected return time $\mathbb{E}_i[T_i] < \infty$ for some, hence all, states $i$ ), then there exists a unique stationary distribution given by

$\pi_i = \frac{1}{\mathbb{E}_i[T_i]}, \quad i \in \mathcal{S},$

where $T_i = \min\{n \geq 1 : X_n = i\}$ is the first return time.
If the chain is transient or null recurrent ( $\mathbb{E}_i[T_i] = \infty$ ), then no stationary distribution exists.

For a finite irreducible chain, positive recurrence is automatic, so a unique stationary distribution always exists.

The stationary probability of state $i$ is inversely proportional to the mean return time: states that take longer to revisit are less likely to be occupied in steady state. For finite chains, every irreducible chain is positive recurrent because there are only finitely many states to wander among.

Proof

Positive recurrence implies existence

Define $\mu_i = \mathbb{E}_i[T_i]$ and set $\pi_i = 1/\mu_i$ . The key step is to show $\boldsymbol{\pi} \mathbf{P} = \boldsymbol{\pi}$ .

Consider the chain started at state $i$ . Between successive visits to $i$ , the chain visits each state $j$ an expected number of times equal to $\sum_{n=1}^{\infty} \mathbb{P}_i(X_n = j, T_i \geq n)$ . Call this $\gamma_j$ . One can show $\gamma = \gamma \mathbf{P}$ and $\gamma_i = 1$ , which implies $\sum_j \gamma_j = \mu_i$ . Setting $\pi_j = \gamma_j / \mu_i$ yields a probability distribution satisfying $\boldsymbol{\pi} = \boldsymbol{\pi} \mathbf{P}$ .

Uniqueness

Suppose $\boldsymbol{\pi}'$ is another stationary distribution. Then for any state $j$ : $\pi_j' = \sum_i \pi_i' p_{ij}^{(n)} \quad \text{for all } n.$

As $n \to \infty$ , by the ergodic theorem (Theorem below), $p_{ij}^{(n)} \to \pi_j$ . Hence $\pi_j' = \sum_i \pi_i' \pi_j = \pi_j$ . So $\boldsymbol{\pi}' = \boldsymbol{\pi}$ .

Transient/null recurrent case

If $\mu_i = \infty$ for all $i$ , any candidate $\boldsymbol{\pi}$ would need $\pi_i = 0$ for all $i$ (since $\pi_i \leq 1/\mu_i = 0$ ), but $\sum_i \pi_i = 1$ is impossible. So no stationary distribution exists. $\blacksquare$

,

Example: Stationary Distribution of the Two-State Chain

Find the stationary distribution of the two-state chain from Example ETwo-State Markov Chain (Sunny/Rainy Weather) with $\mathbf{P} = \begin{pmatrix} 1 - \alpha & \alpha \\ \beta & 1 - \beta \end{pmatrix}$ , where $\alpha = 0.3$ , $\beta = 0.5$ .

Solution

Set up the equations

We need $\boldsymbol{\pi} = \boldsymbol{\pi} \mathbf{P}$ with $\pi_S + \pi_R = 1$ . Writing out:

$\pi_S = (1 - \alpha) \pi_S + \beta \pi_R, \quad \pi_R = \alpha \pi_S + (1 - \beta) \pi_R.$

Both equations simplify to: $\alpha \pi_S = \beta \pi_R$ .

Solve with normalization

From $\alpha \pi_S = \beta \pi_R$ and $\pi_S + \pi_R = 1$ :

$\pi_S = \frac{\beta}{\alpha + \beta} = \frac{0.5}{0.8} = 0.625, \quad \pi_R = \frac{\alpha}{\alpha + \beta} = \frac{0.3}{0.8} = 0.375.$

Interpret

In the long run, it is sunny 62.5% of the time and rainy 37.5%. Note that $\pi_S > \pi_R$ because $\beta > \alpha$ : the chain transitions out of rain faster than out of sun.

Example: Doubly Stochastic Chains

A DTMC on $\mathcal{S} = \{1, 2, \ldots, M\}$ has a doubly stochastic transition matrix (both rows and columns sum to 1). Find the stationary distribution.

Solution

Guess and verify

Let $\boldsymbol{\pi} = (1/M, 1/M, \ldots, 1/M)$ , the uniform distribution. Then:

$[\boldsymbol{\pi} \mathbf{P}]_j = \sum_i \frac{1}{M} p_{ij} = \frac{1}{M} \sum_i p_{ij} = \frac{1}{M},$

since $\sum_i p_{ij} = 1$ (columns sum to 1). So $\boldsymbol{\pi} \mathbf{P} = \boldsymbol{\pi}$ .

Conclusion

Any doubly stochastic irreducible chain has the uniform stationary distribution. This is exploited in algorithm design: random walks on graphs with doubly stochastic transition matrices sample nodes uniformly.

Theorem: Convergence Theorem (Ergodic Theorem for Markov Chains)

Let $\{X_n\}$ be an irreducible, aperiodic, positive recurrent DTMC with stationary distribution $\boldsymbol{\pi}$ . Then for any initial distribution:

$\lim_{n \to \infty} p_{ij}^{(n)} = \pi_j, \quad \text{for all } i, j \in \mathcal{S}.$

In matrix form: $\lim_{n \to \infty} \mathbf{P}^{n} = \mathbf{1} \boldsymbol{\pi}$ , where $\mathbf{1} \boldsymbol{\pi}$ is the matrix with every row equal to $\boldsymbol{\pi}$ .

A chain satisfying all three conditions (irreducible, aperiodic, positive recurrent) is called ergodic.

After sufficiently many steps, the chain "forgets" its initial state and settles into the stationary distribution. Every row of $\mathbf{P}^{n}$ becomes approximately $\boldsymbol{\pi}$ , regardless of the starting state.

Proof

Coupling argument (sketch)

The elegant proof uses coupling: construct two copies of the chain, $(X_n, Y_n)$ , with $X_0 = i$ and $Y_0 \sim \boldsymbol{\pi}$ , evolving under the same transition matrix but coupled so they "meet" (enter the same state) as quickly as possible.

Meeting time

Irreducibility and aperiodicity guarantee that for any two starting states, there exists $n_0$ such that $p_{ij}^{(n_0)} > 0$ for all $i, j$ . This ensures the coupling time $\tau = \inf\{n : X_n = Y_n\}$ is finite almost surely.

After meeting

Once $X_\tau = Y_\tau$ , both chains evolve identically: $X_n = Y_n$ for all $n \geq \tau$ . Since $Y_n \sim \boldsymbol{\pi}$ for all $n$ (stationarity), we get

$|p_{ij}^{(n)} - \pi_j| = |\mathbb{P}(X_n = j) - \mathbb{P}(Y_n = j)| \leq \mathbb{P}(\tau > n) \to 0.$

Hence $p_{ij}^{(n)} \to \pi_j$ as $n \to \infty$ . $\blacksquare$

,

What Happens When the Chain is Periodic?

If the chain is irreducible and positive recurrent but has period $d > 1$ , then $p_{ii}^{(n)}$ does not converge to $\pi_i$ . Instead, $p_{ii}^{(n)}$ is 0 unless $d \mid n$ , and $\lim_{n \to \infty, d \mid n} p_{ii}^{(n)} = d \cdot \pi_i$ . The time-averaged version still holds:

$\frac{1}{n} \sum_{k=0}^{n-1} p_{ij}^{(k)} \to \pi_j \quad \text{as } n \to \infty.$

So the stationary distribution still governs long-run averages, even without pointwise convergence.

Computing and Visualizing the Stationary Distribution

Enter a transition matrix and see its stationary distribution computed as the left eigenvector for eigenvalue 1. Also displays the row distribution of $\mathbf{P}^{n}$ converging to $\boldsymbol{\pi}$ (for ergodic chains).

Parameters

Initial state (0-indexed)0

Track the distribution starting from this state

Historical Note: Perron-Frobenius and the Spectral Theory of Non-negative Matrices

Early 20th century

The existence and uniqueness of the stationary distribution is intimately connected to the Perron-Frobenius theorem (Oskar Perron, 1907; Georg Frobenius, 1912). For a positive (or irreducible non-negative) matrix, this theorem guarantees a unique largest eigenvalue that is real and positive, with a corresponding eigenvector that has all positive entries. For stochastic matrices, this largest eigenvalue is exactly 1, and the corresponding left eigenvector (normalized) is the stationary distribution. Google's PageRank algorithm is arguably the most famous modern application of Perron-Frobenius theory applied to Markov chains.

Quick Check

For a doubly stochastic irreducible chain on 5 states, what is $\pi_3$ ?

$1/3$

$1/5$

Cannot determine without knowing $\mathbf{P}$

$0$

Correction:

1/5

A doubly stochastic chain on $M$ states has uniform stationary distribution $\pi_i = 1/M = 1/5$ for all $i$ .

Common Mistake: Stationary Distribution vs Limiting Distribution

Mistake:

Assuming that if $\boldsymbol{\pi}$ is a stationary distribution, then $p_{ij}^{(n)} \to \pi_j$ . This conflates existence of $\boldsymbol{\pi}$ with convergence.

Correction:

Convergence $p_{ij}^{(n)} \to \pi_j$ requires aperiodicity in addition to irreducibility and positive recurrence. A periodic chain has a stationary distribution but $p_{ij}^{(n)}$ oscillates and does not converge pointwise.

Key Takeaway

An irreducible, positive recurrent DTMC has a unique stationary distribution $\boldsymbol{\pi}$ with $\pi_i = 1/\mathbb{E}_i[T_i]$ . Adding aperiodicity gives the convergence theorem: $\mathbf{P}^{n} \to \mathbf{1}\boldsymbol{\pi}$ . For finite irreducible chains, positive recurrence is automatic — only aperiodicity needs checking.

Stationary Distribution

Long-Run Behavior

Definition: Stationary (Invariant) Distribution

Stationary distribution

Theorem: Existence and Uniqueness of the Stationary Distribution

Positive recurrence implies existence

Uniqueness

Transient/null recurrent case

Example: Stationary Distribution of the Two-State Chain

Set up the equations

Solve with normalization

Interpret

Example: Doubly Stochastic Chains

Guess and verify

Conclusion

Theorem: Convergence Theorem (Ergodic Theorem for Markov Chains)

Coupling argument (sketch)

Meeting time

After meeting

What Happens When the Chain is Periodic?

Computing and Visualizing the Stationary Distribution

Parameters

Historical Note: Perron-Frobenius and the Spectral Theory of Non-negative Matrices

Quick Check

Common Mistake: Stationary Distribution vs Limiting Distribution

Key Takeaway

Definition:
Stationary (Invariant) Distribution