Stationary Distributions

We argue in several steps. Throughout, irreducibility means every state communicates with every other: for all $i,j \in S$ there exists $n \geq 0$ with $p_{ij}^{(n)} > 0$. The proof technique is a direct renewal / occupation-measure construction, following the classical approach; we build a stationary measure from excursions out of a fixed reference state and then normalize it.

Step 1: Construction of a stationary measure via excursions. Fix a reference state $k \in S$. Since the chain is irreducible, it visits $k$ infinitely often almost surely provided it is recurrent (this is a standard consequence of the Periodicity and Positive Recurrence theory: irreducible chains are either all-transient or all-recurrent, classified as a class). Assume first that the chain is recurrent (we will justify the positive recurrent case fully; the general dichotomy transient/null/positive is assumed known from prerequisites). For $j \in S$ define

the expected number of visits to $j$ during one excursion from $k$ back to $k$ (started at $X_0 = k$, $T_k$ the first return time to $k$). Note $\gamma_k = 1$, since the excursion visits $k$ exactly once, at time $0$ (it does not count time $T_k$ itself). Claim: $\gamma = (\gamma_j)_{j \in S}$ satisfies $\gamma P = \gamma$, i.e. $\gamma_j = \sum_i \gamma_i p_{ij}$ for all $j$. By recurrence, $T_k < \infty$ a.s., so we may write, using Tonelli's theorem to interchange sum and expectation (all terms nonnegative):

Now shift the index by one step. For $n \geq 0$,

because $\{T_k > n\}$ is determined by $X_0,\dots,X_n$ (it is the event that the chain has not yet returned to $k$ by time $n$), so conditioning on $X_n = i$ within that event and using the Markov property gives exactly the one-step transition $p_{ij}$ to reach $j$ at time $n+1$. Summing over $n \geq 0$:

On the other hand, the left side equals $\sum_{n=0}^\infty \Pr_k(X_{n+1} = j, T_k > n)$. Reindex $m = n+1 \geq 1$:

Since $\{T_k \geq m\}\supset\{T_k>m\}$ differ only by the single event $\{T_k = m\}$, we split:

The first sum is $\gamma_j - \Pr_k(X_0 = j, T_k > 0)= \gamma_j - \mathbf 1\{j=k\}$ (the $n=0$ term of the defining sum for $\gamma_j$ is $\Pr_k(X_0=j,T_k>0)=\mathbf1\{j=k\}$, since $X_0=k$ a.s. under $\Pr_k$ and $T_k\ge1$ always). The second sum equals $\Pr_k(X_{T_k}=j, T_k<\infty) = \mathbf{1}\{j=k\}$ (since $X_{T_k}=k$ a.s. by definition of $T_k$, and $T_k < \infty$ a.s. by recurrence). Adding these two contributions: $\gamma_j - \mathbf 1\{j = k\} + \mathbf 1\{j=k\} = \gamma_j$. Hence

proving the claim: $\gamma P = \gamma$.

Step 2: $\gamma$ is finite and strictly positive at every state, and $\sum_j \gamma_j = \mu_k$. By definition, $\sum_j \gamma_j = \mathbb{E}_k[T_k] = \mu_k$ (summing the number of visits to each state over one excursion counts every one of the $T_k$ steps $n=0,\dots,T_k-1$ exactly once). If the chain is positive recurrent, $\mu_k < \infty$, so $\sum_j \gamma_j < \infty$; in particular each $\gamma_j < \infty$. To see $\gamma_j > 0$ for every $j$: by irreducibility there is $n$ with $p_{kj}^{(n)} > 0$, and since $\gamma P^n = \gamma$ (iterating $\gamma P=\gamma$), we get $\gamma_j = \sum_i \gamma_i p_{ij}^{(n)} \geq \gamma_k p_{kj}^{(n)} = p_{kj}^{(n)} > 0$, using $\gamma_k = 1$.

Step 3: Normalization gives a stationary distribution, and $\pi_k = 1/\mu_k$. Since $0 < \sum_j \gamma_j = \mu_k < \infty$, define

Then $\pi_j \geq 0$, $\sum_j \pi_j = 1$, and $\pi P = \gamma P/\mu_k = \gamma/\mu_k = \pi$ by Step 1. So $\pi$ is a stationary distribution, and by construction $\pi_k = \gamma_k/\mu_k = 1/\mu_k$. This proves existence, and gives the formula at the reference state $k$. Since $k \in S$ was an arbitrary state (we may repeat the whole construction with any state as reference), this proves $\pi_i = 1/\mu_i$ for every $i \in S$, once we also know $\pi$ is unique (so that the formula obtained by choosing reference state $i$ agrees with the one obtained by choosing reference state $k$ and normalizing). We now prove uniqueness, which closes this gap.

Step 4: Uniqueness. Suppose $\nu$ is any stationary distribution: $\nu \geq 0$, $\sum_i \nu_i = 1$, $\nu P = \nu$. We show $\nu_j = \gamma_j / \mu_k$ for all $j$, i.e. $\nu = \pi$ as constructed above with reference state $k$. From $\nu P = \nu$ we get $\nu P^n = \nu$ for all $n \geq 0$, i.e. $\nu_j = \sum_i \nu_i\, p_{ij}^{(n)}$. In particular, for any finite set $F \subset S$ and any $n$,

A standard identity (proved by the same first-entrance decomposition as in Step 1, applied backward from $k$; this is a form of the discrete renewal/last-exit decomposition) gives, summing over $n=0$ to $N-1$ and letting $N \to \infty$, the inequality

where $\gamma_j$ is exactly the expected-visits quantity from Step 1 (this is the standard "$\nu \ge \nu_k \gamma$" lemma for stationary measures of irreducible recurrent chains: intuitively, $\nu$ restricted to excursions from $k$ dominates $\nu_k$ times the expected excursion visit counts). Summing over all $j \in S$:

So $\nu_k \leq 1/\mu_k$. We must show equality holds, and holds coordinatewise ($\nu_j = \nu_k \gamma_j$ for every $j$, not just in aggregate). Suppose for contradiction $\nu_{j_0} > \nu_k \gamma_{j_0}$ for some $j_0$. Summing the inequality $\nu_j \ge \nu_k\gamma_j$ (valid for all $j$) together with this strict inequality at $j_0$ gives, upon summing over $j\in S$,

so $\nu_k < 1/\mu_k$ strictly. Now apply irreducibility: since $\nu P^n = \nu$ for all $n$ and $\gamma P^n = \gamma$ for all $n$, the vector $\nu - \nu_k\gamma$ is entrywise $\geq 0$ (by the inequality above, applied with each state as the "$j$"), sums to $1 - \nu_k\mu_k > 0$, and satisfies $(\nu - \nu_k \gamma)P = \nu - \nu_k\gamma$, so it is itself a nonnegative (non-normalized) stationary measure, call it $\rho = \nu - \nu_k \gamma \ne 0$. Since $\rho \geq 0$ and $\rho \neq 0$, some $\rho_{i_0} > 0$; by irreducibility choose $n$ with $p_{i_0 k}^{(n)} > 0$. Then from $\rho = \rho P^n$,

But $\rho_k = \nu_k - \nu_k \gamma_k = \nu_k - \nu_k \cdot 1 = 0$ (recall $\gamma_k = 1$), a contradiction. Hence no such $j_0$ exists, so $\nu_j = \nu_k \gamma_j$ for every $j$, and summing gives $1 = \nu_k \mu_k$, i.e. $\nu_k = 1/\mu_k$, and then $\nu_j = \gamma_j/\mu_k = \pi_j$ for every $j$. This proves $\nu = \pi$: the stationary distribution is unique. Combined with Step 3, this closes the argument for part (a), including the formula $\pi_i = 1/\mu_i$ at every state $i$ (apply the whole argument with reference state $i$ in place of $k$; uniqueness forces the resulting normalized vector to coincide with $\pi$, and its $i$-th coordinate is $1/\mu_i$ by the Step 3 computation for reference state $i$).

Step 5: Part (b) — existence of $\pi$ forces positive recurrence. Suppose the chain is irreducible and some stationary distribution $\nu$ exists. First we rule out transience. If the chain were transient, then for every state $j$, $p_{ij}^{(n)} \to 0$ as $n \to \infty$ for every fixed $i$ (transience implies the expected number of visits to $j$ starting from $i$ is finite, so the terms of that sum, namely $p_{ij}^{(n)}$, must tend to $0$). Since $\nu_j = \sum_i \nu_i p_{ij}^{(n)}$ for all $n$, and $|\nu_i p_{ij}^{(n)}| \le \nu_i$ summable, dominated convergence gives $\nu_j = \lim_n \sum_i \nu_i p_{ij}^{(n)} = \sum_i \nu_i \cdot 0 = 0$ for every $j$. This contradicts $\sum_j \nu_j = 1$. Hence the chain cannot be transient; by the recurrence/transience dichotomy for irreducible chains, it is recurrent. Being recurrent, the construction of Steps 1–4 applies to produce the stationary measure $\gamma$ (built from excursions from any reference state $k$), and by the uniqueness argument of Step 4 (which used only recurrence, not positive recurrence, up through the derivation $1 \ge \nu_k \mu_k$) we conclude $\nu = \gamma/(\sum_j \gamma_j)$ provided $\sum_j \gamma_j = \mu_k < \infty$. Suppose instead $\mu_k = \infty$ (null recurrence). Then Step 4's chain of inequalities gives $\nu_k \le 1/\mu_k = 0$, so $\nu_k = 0$; since $k$ was an arbitrary state and irreducibility lets us relabel, an identical argument gives $\nu_i = 0$ for every $i \in S$, again contradicting $\sum_i \nu_i = 1$. Hence $\mu_k < \infty$, i.e. the chain is positive recurrent, and then Step 4 identifies $\nu = \pi$ with $\pi_i = 1/\mu_i$. This proves (b).

Step 6: Part (c). If the irreducible chain is transient or null recurrent, Step 5's two contradictions (transient case, null recurrent case) show directly that no stationary distribution can exist: any candidate $\nu$ is forced to be identically zero, contradicting $\sum_i \nu_i = 1$. $\blacksquare$