2  Markov chains

The hidden layer of an HMM is a Markov chain, and most of what can be said about an HMM’s long-run behaviour comes from what can be said about that chain. This chapter develops the finite-state theory to the level the rest of the notes needs: enough to state the ergodic theorem used for consistency in Chapter 8, and enough spectral machinery to quantify how quickly the chain forgets where it started.

Zucchini et al. (2016, ch. 1) covers the same ground at an applied level. The treatment here adds proofs and keeps the notation compatible.

By the end of this chapter you will be able to

• check whether a transition matrix is irreducible and aperiodic, and say what each buys;
• state the ergodic theorem and explain why it needs irreducibility but not aperiodicity;
• bound the distance to stationarity using either the spectral gap or Dobrushin’s coefficient, and say when each applies;
• explain why a time-inhomogeneous chain can still forget its initial condition.

NoteWhere this chapter leads

The ergodic theorem (Theorem 2.2) turns time averages into expectations, and it is the engine behind consistency of the maximum likelihood estimator. The contraction results (Theorem 2.3, Proposition 2.5) reappear as filter stability: an HMM filter initialised at the wrong distribution recovers at a geometric rate, which is why misspecifying \(\boldsymbol{\delta}\) costs so little in practice.

2.1 Definition and basic structure

2.1.1 The Markov property

Definition 2.1 (Time-homogeneous Markov chain) Let \(E = \{1,\dots,K\}\). A process \((S_t)_{t \ge 1}\) with values in \(E\) is a time-homogeneous Markov chain with transition matrix \(\boldsymbol{\Gamma} = (\gamma_{ij})\) and initial distribution \(\boldsymbol{\delta} \in \Delta^{K-1}\) if \(\mathbb{P}(S_1 = i) = \delta_i\) and, for every \(t \ge 1\) and every \(i_1,\dots,i_t,j\) with \(\mathbb{P}(S_{1:t} = i_{1:t}) > 0\), \[ \mathbb{P}(S_{t+1} = j \mid S_{1:t} = i_{1:t}) = \mathbb{P}(S_{t+1} = j \mid S_t = i_t) = \gamma_{i_t j} . \]

The condition says the future depends on the past only through the present. It has an equivalent product form that is often easier to work with.

Proposition 2.1 (Finite-dimensional distributions) \((S_t)\) is a Markov chain with parameters \((\boldsymbol{\delta}, \boldsymbol{\Gamma})\) if and only if, for every \(T \ge 1\) and every \(i_{1:T} \in E^T\), \[ \mathbb{P}(S_{1:T} = i_{1:T}) = \delta_{i_1} \prod_{t=1}^{T-1} \gamma_{i_t i_{t+1}} . \]

Proof. For the forward direction, apply the chain rule \(\mathbb{P}(S_{1:T} = i_{1:T}) = \mathbb{P}(S_1 = i_1) \prod_{t=1}^{T-1} \mathbb{P}(S_{t+1} = i_{t+1} \mid S_{1:t} = i_{1:t})\) and replace each conditional factor using Definition 2.1. For the converse, sum the product expression over \(i_{T}\) to check consistency, then form the ratio of the expressions for \(\mathbb{P}(S_{1:t+1})\) and \(\mathbb{P}(S_{1:t})\); every factor cancels except \(\gamma_{i_t i_{t+1}}\), which does not depend on \(i_{1:t-1}\).

This factorisation is the hidden-state half of the HMM likelihood in Chapter 3. The observation half multiplies in one emission factor per time point.

2.1.2 Chapman–Kolmogorov

Write \(\gamma^{(n)}_{ij} = \mathbb{P}(S_{t+n} = j \mid S_t = i)\) for the \(n\)-step transition probabilities, which by homogeneity do not depend on \(t\).

Proposition 2.2 (Chapman–Kolmogorov equations) For all \(m, n \ge 0\), \(\ \boldsymbol{\Gamma}^{(m+n)} = \boldsymbol{\Gamma}^{(m)} \boldsymbol{\Gamma}^{(n)}\), and consequently \(\boldsymbol{\Gamma}^{(n)} = \boldsymbol{\Gamma}^n\).

Proof. Condition on the state at the intermediate time and use the Markov property: \[ \gamma^{(m+n)}_{ij} = \sum_{k \in E} \mathbb{P}(S_{m+n} = j \mid S_m = k) \, \mathbb{P}(S_m = k \mid S_0 = i) = \sum_{k} \gamma^{(m)}_{ik} \gamma^{(n)}_{kj}. \] The second claim follows by induction from \(\boldsymbol{\Gamma}^{(1)} = \boldsymbol{\Gamma}\).

So the entire temporal structure of the chain is encoded in the powers of a single matrix, and the spectral theory of Chapter 1 applies directly.

2.1.3 Stationary distributions

Definition 2.2 (Stationary distribution) A vector \(\boldsymbol{\pi} \in \Delta^{K-1}\) is a stationary distribution for \(\boldsymbol{\Gamma}\) if \(\boldsymbol{\pi}^\top \boldsymbol{\Gamma} = \boldsymbol{\pi}^\top\).

If \(S_1 \sim \boldsymbol{\pi}\) then \(S_t \sim \boldsymbol{\pi}\) for every \(t\), and the whole process is strictly stationary. Existence on a finite state space is automatic: \(\boldsymbol{\Gamma}\) maps the compact convex set \(\Delta^{K-1}\) into itself continuously, so Brouwer’s fixed point theorem supplies a fixed vector. Uniqueness needs irreducibility, which we come to next.

2.1.4 Reversibility

Definition 2.3 (Reversibility and detailed balance) A chain with transition matrix \(\boldsymbol{\Gamma}\) and stationary distribution \(\boldsymbol{\pi}\) is reversible if \[ \pi_i \gamma_{ij} = \pi_j \gamma_{ji} \qquad \text{for all } i,j \in E . \]

Detailed balance says the equilibrium flow from \(i\) to \(j\) matches the flow from \(j\) to \(i\). Summing over \(i\) recovers stationarity, so detailed balance is the stronger condition. Its value is spectral.

Proposition 2.3 (Self-adjointness under reversibility) Equip \(\mathbb{R}^E\) with the inner product \(\langle f, g \rangle_{\boldsymbol{\pi}} = \sum_i \pi_i f(i) g(i)\) and let \((\boldsymbol{\Gamma} f)(i) = \sum_j \gamma_{ij} f(j)\). If the chain is reversible with \(\pi_i > 0\) for all \(i\), then \(\boldsymbol{\Gamma}\) is self-adjoint on \(L^2(\boldsymbol{\pi})\), so its eigenvalues are real and lie in \([-1,1]\) and it admits a \(\boldsymbol{\pi}\)-orthonormal eigenbasis.

Proof. Expand and apply detailed balance: \[ \langle f, \boldsymbol{\Gamma} g \rangle_{\boldsymbol{\pi}} = \sum_{i,j} \pi_i \gamma_{ij} f(i) g(j) = \sum_{i,j} \pi_j \gamma_{ji} f(i) g(j) = \langle \boldsymbol{\Gamma} f, g \rangle_{\boldsymbol{\pi}} . \] The spectral theorem for self-adjoint operators on a finite-dimensional inner product space gives the rest; the eigenvalue bound follows because \(\lVert \boldsymbol{\Gamma} \rVert_\infty = 1\).

Hidden chains in HMMs are not assumed reversible, and estimated transition matrices rarely satisfy detailed balance. Reversible chains remain useful as a source of examples where mixing rates can be computed exactly.

2.2 Ergodic theory

2.2.1 Communication and irreducibility

Write \(i \rightsquigarrow j\) when \(\gamma^{(n)}_{ij} > 0\) for some \(n \ge 0\), and \(i \leftrightarrow j\) when both \(i \rightsquigarrow j\) and \(j \rightsquigarrow i\). The relation \(\leftrightarrow\) is an equivalence relation, and its classes are the communicating classes of the chain.

Definition 2.4 (Irreducibility) A chain is irreducible if \(E\) is a single communicating class, that is, every state can be reached from every other.

For an HMM, irreducibility of the hidden chain is a modelling assumption with real content. It rules out absorbing states and transient start-up states, guarantees a unique stationary distribution, and is a standing hypothesis in the identifiability and consistency results of Chapters 6 and 8.

2.2.2 Periodicity

Definition 2.5 (Period) The period of \(i \in E\) is \(d(i) = \gcd \{ n \ge 1 : \gamma^{(n)}_{ii} > 0 \}\). A chain is aperiodic if \(d(i) = 1\) for some, hence every, state.

Proposition 2.4 (Period is a class property) If \(i \leftrightarrow j\) then \(d(i) = d(j)\).

Proof. Choose \(m, n\) with \(\gamma^{(m)}_{ij} > 0\) and \(\gamma^{(n)}_{ji} > 0\), so \(\gamma^{(m+n)}_{ii} > 0\) and \(d(i)\) divides \(m+n\). For any \(r\) with \(\gamma^{(r)}_{jj} > 0\) we get \(\gamma^{(m+r+n)}_{ii} > 0\), so \(d(i)\) divides \(m + r + n\) and hence divides \(r\). Therefore \(d(i)\) divides \(d(j)\), and the reverse follows by symmetry.

A chain with period \(d > 1\) cycles deterministically between \(d\) subsets of the state space, and \(\mathbb{P}(S_t = \cdot)\) never settles down. Aperiodicity excludes that. Together, irreducibility and aperiodicity are exactly primitivity of \(\boldsymbol{\Gamma}\) in the sense of Definition 1.9, which connects the probabilistic conditions to the Perron–Frobenius theorem.

2.2.3 Convergence to equilibrium

Theorem 2.1 (Convergence theorem) Let \(\boldsymbol{\Gamma}\) be irreducible and aperiodic. Then \(\boldsymbol{\Gamma}\) has a unique stationary distribution \(\boldsymbol{\pi}\), it satisfies \(\pi_i > 0\) for all \(i\), and for every initial distribution \(\boldsymbol{\delta}\), \[ \lim_{t \to \infty} \bigl\lVert \boldsymbol{\delta}^\top \boldsymbol{\Gamma}^t - \boldsymbol{\pi}^\top \bigr\rVert_{\mathrm{TV}} = 0 , \] where \(\lVert \mu - \nu \rVert_{\mathrm{TV}} = \tfrac12 \sum_i |\mu_i - \nu_i|\). The convergence is geometric.

Irreducibility plus aperiodicity makes \(\boldsymbol{\Gamma}\) primitive, so Theorem 1.2 gives a simple eigenvalue \(1\) with strictly positive left eigenvector, every other eigenvalue strictly smaller in modulus, and the geometric rate of Proposition 1.2. Levin and Peres (2017, ch. 4) gives a coupling proof that avoids diagonalisability altogether.

2.2.4 The ergodic theorem

Theorem 2.2 (Ergodic theorem for finite chains) Let \((S_t)\) be irreducible with stationary distribution \(\boldsymbol{\pi}\), started from any initial distribution. For every \(f \colon E \to \mathbb{R}\), \[ \frac{1}{T} \sum_{t=1}^{T} f(S_t) \; \xrightarrow[T \to \infty]{\text{a.s.}} \; \mathbb{E}_{\boldsymbol{\pi}}[f(S)] = \sum_{i \in E} \pi_i f(i) . \]

Proof. Fix a state \(i\) and let \(\tau_1 < \tau_2 < \dots\) be the successive return times to \(i\). By irreducibility on a finite state space these are almost surely finite with finite mean, and the strong Markov property makes the excursion blocks between consecutive returns independent and identically distributed. Applying the strong law of large numbers to the block sums of \(f\) and separately to the block lengths, the ratio converges almost surely to \(\mathbb{E}_i[\sum_{t < \tau_1} f(S_t)] / \mathbb{E}_i[\tau_1]\), which is the standard renewal-theoretic expression for \(\mathbb{E}_{\boldsymbol{\pi}}[f]\). Bounding the contribution of the incomplete final block by \(\lVert f \rVert_\infty \tau_{n+1}/T \to 0\) finishes the argument. See Levin and Peres (2017, ch. 4) for details.

Note that aperiodicity is not required: time averages converge even when the distribution at a fixed time does not. This is the version needed in Chapter 8, where the normalised log-likelihood is a time average along the trajectory of an ergodic process.

2.3 Quantifying the rate

Knowing that the chain converges is rarely enough; the asymptotic theory needs a rate, because the error terms in a central limit theorem are controlled by how quickly dependence decays.

2.3.1 Mixing time

Definition 2.6 (Mixing time) With \(\boldsymbol{\mu}_t(\boldsymbol{\delta}) = \boldsymbol{\delta}^\top \boldsymbol{\Gamma}^t\), the mixing time at accuracy \(\varepsilon > 0\) is \[ t_{\mathrm{mix}}(\varepsilon) = \min \Bigl\{ t \ge 0 : \ \sup_{\boldsymbol{\delta} \in \Delta^{K-1}} \lVert \boldsymbol{\mu}_t(\boldsymbol{\delta}) - \boldsymbol{\pi} \rVert_{\mathrm{TV}} \le \varepsilon \Bigr\} . \]

Proposition 2.5 (Spectral bound on mixing) For a reversible, irreducible, aperiodic chain with absolute spectral gap \(\varrho = 1 - |\lambda_2|\) and \(\pi_{\min} = \min_i \pi_i\), \[ \lVert \boldsymbol{\mu}_t(\boldsymbol{\delta}) - \boldsymbol{\pi} \rVert_{\mathrm{TV}} \;\le\; \frac{(1-\varrho)^t}{2\sqrt{\pi_{\min}}} , \qquad\text{hence}\qquad t_{\mathrm{mix}}(\varepsilon) \le \frac{1}{\varrho} \log \frac{1}{2 \varepsilon \sqrt{\pi_{\min}}} . \]

The bound is proved by expanding \(\boldsymbol{\delta}^\top \boldsymbol{\Gamma}^t\) in the \(\boldsymbol{\pi}\)-orthonormal eigenbasis supplied by Proposition 2.3 and applying Cauchy–Schwarz to pass from \(\ell^2(\boldsymbol{\pi})\) to total variation; Levin and Peres (2017, ch. 12) has the details. The shape is what matters: the relaxation time \(1/\varrho\) sets the timescale, and the dependence on \(\pi_{\min}\) enters only logarithmically.

2.3.2 Coupling

Coupling gives bounds without any spectral assumption.

Definition 2.7 (Coupling) A coupling of two chains with transition matrix \(\boldsymbol{\Gamma}\) and initial distributions \(\boldsymbol{\delta}, \boldsymbol{\delta}'\) is a process \((S_t, S'_t)\) on a common probability space whose marginals are the two chains. Its coalescence time is \(\tau = \inf\{ t \ge 0 : S_t = S'_t \}\), and the coupling is such that \(S_s = S'_s\) for all \(s \ge \tau\).

Proposition 2.6 (Coupling inequality) For any such coupling and every \(t \ge 0\), \[ \bigl\lVert \boldsymbol{\delta}^\top \boldsymbol{\Gamma}^t - (\boldsymbol{\delta}')^\top \boldsymbol{\Gamma}^t \bigr\rVert_{\mathrm{TV}} \le \mathbb{P}(\tau > t) . \]

Proof. For any \(A \subseteq E\), the events \(\{S_t \in A\}\) and \(\{S'_t \in A\}\) agree on \(\{\tau \le t\}\), so their probabilities differ by at most \(\mathbb{P}(\tau > t)\). Taking the supremum over \(A\) gives the total variation distance.

Constructing a coupling that coalesces quickly then gives a mixing bound directly. The same idea, applied to two filters started from different initial distributions, is how filter stability is proved in Chapter 5.

2.3.3 Dobrushin’s coefficient

Definition 2.8 (Dobrushin contraction coefficient) For a stochastic matrix \(\boldsymbol{\Gamma}\), \[ \kappa(\boldsymbol{\Gamma}) = \frac{1}{2} \max_{i,i' \in E} \sum_{j \in E} \bigl| \gamma_{ij} - \gamma_{i'j} \bigr| \;=\; \max_{i, i'} \bigl\lVert \boldsymbol{\Gamma}_{i,\cdot} - \boldsymbol{\Gamma}_{i',\cdot} \bigr\rVert_{\mathrm{TV}} \in [0,1] . \]

Theorem 2.3 (Dobrushin contraction) For any probability vectors \(\boldsymbol{\mu}, \boldsymbol{\nu}\) on \(E\), \[ \bigl\lVert \boldsymbol{\mu}^\top \boldsymbol{\Gamma} - \boldsymbol{\nu}^\top \boldsymbol{\Gamma} \bigr\rVert_{\mathrm{TV}} \;\le\; \kappa(\boldsymbol{\Gamma}) \, \lVert \boldsymbol{\mu} - \boldsymbol{\nu} \rVert_{\mathrm{TV}} , \] and \(\kappa\) is submultiplicative: \(\kappa(\boldsymbol{\Gamma}_1 \boldsymbol{\Gamma}_2) \le \kappa(\boldsymbol{\Gamma}_1)\kappa(\boldsymbol{\Gamma}_2)\).

Two features make this more useful than the spectral bound in the HMM setting. It needs no reversibility, no diagonalisability and no stationary distribution. And because it is submultiplicative, it applies verbatim to products of different transition matrices, which is exactly the situation for time-inhomogeneous chains and for the observation-dependent operators that appear inside the forward recursion. A sufficient condition for \(\kappa(\boldsymbol{\Gamma}) < 1\) is the Doeblin minorisation \(\gamma_{ij} \ge \epsilon \, \nu_j\) for all \(i, j\), some \(\epsilon > 0\) and a probability vector \(\boldsymbol{\nu}\); then \(\kappa(\boldsymbol{\Gamma}) \le 1 - \epsilon\).

2.4 Time-inhomogeneous chains

Some extensions replace \(\boldsymbol{\Gamma}\) by a sequence \((\boldsymbol{\Gamma}_t)\), with \(\mathbb{P}(S_{t+1} = j \mid S_t = i) = (\boldsymbol{\Gamma}_t)_{ij}\). This covers HMMs whose transition probabilities depend on covariates, a construction used throughout Zucchini et al. (2016, ch. 12) and again in the hierarchical models of Chapter 10.

Define the composite kernel \(\boldsymbol{\Gamma}_{s,t} = \boldsymbol{\Gamma}_s \boldsymbol{\Gamma}_{s+1} \cdots \boldsymbol{\Gamma}_{t-1}\) for \(s < t\). The Chapman–Kolmogorov identity survives as \(\boldsymbol{\Gamma}_{s,u} = \boldsymbol{\Gamma}_{s,t} \boldsymbol{\Gamma}_{t,u}\) for \(s < t < u\), but stationary distributions generally do not exist, so the questions change: instead of asking where the chain settles, we ask whether it forgets its initial condition.

Proposition 2.7 (Loss of memory) If \(\kappa(\boldsymbol{\Gamma}_t) \le 1 - \epsilon\) for every \(t\) and some \(\epsilon > 0\), then for any initial distributions \(\boldsymbol{\mu}, \boldsymbol{\nu}\), \[ \bigl\lVert \boldsymbol{\mu}^\top \boldsymbol{\Gamma}_{1,t} - \boldsymbol{\nu}^\top \boldsymbol{\Gamma}_{1,t} \bigr\rVert_{\mathrm{TV}} \le (1-\epsilon)^{t-1} \lVert \boldsymbol{\mu} - \boldsymbol{\nu} \rVert_{\mathrm{TV}} \; \longrightarrow \; 0 . \]

This follows from Theorem 2.3 by submultiplicativity. The uniform lower bound on transition probabilities is a Doeblin condition, and it is the standard hypothesis in the filter stability literature; Cappé et al. (2005, ch. 4) and Del Moral and Guionnet (2001) develop the consequences for HMMs.

Check your understanding. The chain with transition matrix \(\bigl(\begin{smallmatrix} 0 & 1 \\ 1 & 0\end{smallmatrix}\bigr)\) is irreducible. Does \(\mathbb{P}(S_t = 1)\) converge? Does \(T^{-1}\sum_t \mathbf{1}\{S_t = 1\}\) converge?

TipShow answer

The chain alternates deterministically, so it has period 2 and is not aperiodic. Started from \(S_1 = 1\), \(\mathbb{P}(S_t = 1)\) alternates between \(1\) and \(0\) forever and never converges — Theorem 2.1 does not apply.

The time average does converge, to \(1/2 = \pi_1\). Theorem 2.2 requires only irreducibility, which is exactly why it is the version needed in Chapter 8: the normalised log-likelihood is a time average along a single trajectory, and periodicity does not disturb it.

Note also that \(\kappa(\boldsymbol{\Gamma}) = 1\) here, so Theorem 2.3 gives no contraction — correctly, since this chain never forgets where it started.

2.5 Summary

• A finite-state Markov chain is determined by \((\boldsymbol{\delta}, \boldsymbol{\Gamma})\), and its finite-dimensional distributions factorise as a product of one initial term and one transition term per step (Proposition 2.1).
• Irreducibility gives a unique stationary distribution; adding aperiodicity gives convergence to it from any starting point (Theorem 2.1).
• Time averages converge almost surely to expectations under \(\boldsymbol{\pi}\) whenever the chain is irreducible (Theorem 2.2), with no aperiodicity needed.
• Rates come from the spectral gap under reversibility (Proposition 2.5), or from coupling and Dobrushin’s coefficient in general (Theorem 2.3). The latter extends to time-inhomogeneous chains and to the filter recursions of Chapter 5.

2.6 Further reading

Levin and Peres (2017) is the standard modern reference for finite-state chains and mixing times, with coupling arguments given in full. Seneta (2006) approaches the same material through non-negative matrices, and includes a detailed treatment of Dobrushin’s coefficient. For general state spaces, Meyn and Tweedie (2009) is the canonical source. Cappé et al. (2005, ch. 4) specialises the theory to the operators that arise in HMM filtering, and Zucchini et al. (2016, ch. 1) gives a compact applied account with the same notation used here.

Cappé, Olivier, Éric Moulines, and Tobias Rydén. 2005. Inference in Hidden Markov Models. Springer Series in Statistics. Springer. https://doi.org/10.1007/0-387-28982-8.

Del Moral, Pierre, and Alice Guionnet. 2001. “On the Stability of Interacting Processes with Applications to Filtering and Genetic Algorithms.” Annales de l’Institut Henri Poincaré (B) Probability and Statistics 37 (2): 155–94. https://doi.org/10.1016/S0246-0203(00)01064-5.

Levin, David A., and Yuval Peres. 2017. Markov Chains and Mixing Times. 2nd ed. American Mathematical Society. https://doi.org/10.1090/mbk/107.

Meyn, Sean, and Richard L. Tweedie. 2009. Markov Chains and Stochastic Stability. 2nd ed. Cambridge University Press. https://doi.org/10.1017/CBO9780511626630.

Seneta, Eugene. 2006. Non-Negative Matrices and Markov Chains. Revised. Springer. https://doi.org/10.1007/0-387-32792-4.

Zucchini, Walter, Iain L. MacDonald, and Roland Langrock. 2016. Hidden Markov Models for Time Series: An Introduction Using R. 2nd ed. Chapman; Hall/CRC. https://doi.org/10.1201/b20790.