1  Probability and linear algebra

A hidden Markov model is a statement about conditional independence, and almost every result in these notes is obtained by rewriting a conditional expectation. This chapter fixes the language for doing that. It is a reference chapter rather than a course in measure theory: the aim is to make later arguments precise, not to develop probability from the axioms.

Three bodies of material get used repeatedly. Conditional expectation and conditional distributions justify writing things like \(\mathbb{P}(S_t = i \mid Y_{1:T} = y_{1:T})\) and manipulating them. Spectral theory for non-negative matrices controls how fast a Markov chain forgets its starting point, which is what makes both the ergodic theory of Chapter 8 and the filter stability results of Chapter 5 work. Convex analysis on the simplex explains why the EM algorithm of Chapter 6 increases the likelihood at every step.

By the end of this chapter you will be able to

• state what conditional expectation is and use the tower property to manipulate it;
• explain why conditioning on \(\{Y_{1:T} = y_{1:T}\}\) makes sense even when that event has probability zero;
• read off the stationary distribution and convergence rate of a stochastic matrix from its spectrum;
• recognise Kullback–Leibler divergence as a Bregman divergence and use its non-negativity.

NotePrerequisites

Undergraduate probability (random variables, conditional probability, the law of large numbers), linear algebra through eigenvalues and eigenvectors, and calculus. Measure theory is used but not assumed; every measure-theoretic object here is introduced where it is needed. Williams (1991) and Kallenberg (2021) are the standard places to fill gaps.

1.1 Probability spaces and random elements

1.1.1 The underlying space

Definition 1.1 (Probability space) A probability space is a triple \((\Omega, \mathcal{F}, \mathbb{P})\) in which \(\Omega\) is a set of outcomes, \(\mathcal{F} \subseteq 2^{\Omega}\) is a \(\sigma\)-algebra (it contains \(\Omega\) and is closed under complements and countable unions), and \(\mathbb{P} \colon \mathcal{F} \to [0,1]\) is countably additive with \(\mathbb{P}(\Omega) = 1\).

The \(\sigma\)-algebra is the set of statements to which the model assigns a probability. In a finite-state HMM the hidden states take values in \(E = \{1, \dots, K\}\) with the discrete \(\sigma\)-algebra, so every subset is measurable and nothing can go wrong. The formalism still earns its place, for two reasons.

First, an HMM is a statement about an infinite sequence \((S_t, Y_t)_{t \ge 1}\), and the law of that sequence lives on a product space. For a measurable space \((S, \mathcal{S})\), the countable product \((S^{\mathbb{N}}, \mathcal{S}^{\otimes \mathbb{N}})\) carries the smallest \(\sigma\)-algebra making every coordinate projection measurable. Kolmogorov’s extension theorem says that a consistent family of finite-dimensional distributions — exactly what Chapter 3 writes down — determines a unique measure on that product space. Without it, “the process \((S_t)_{t \ge 1}\)” would be an abuse of notation.

Second, the observation space is usually not discrete. Once \(Y_t\) takes values in \(\mathbb{R}^d\), conditioning on \(\{Y_{1:T} = y_{1:T}\}\) conditions on an event of probability zero, and the naive definition of conditional probability divides by zero. Sections 1.2 and 1.3 repair this.

1.1.2 Random variables and their laws

Definition 1.2 (Random element) Let \((S, \mathcal{S})\) be a measurable space. A random element of \(S\) is a measurable map \(X \colon (\Omega, \mathcal{F}) \to (S, \mathcal{S})\). Its law is the pushforward measure \(\mathbb{P}_X(A) = \mathbb{P}(X \in A)\) for \(A \in \mathcal{S}\).

When \(S = \mathbb{R}\) we say random variable, and when \(S = \mathbb{R}^d\) random vector. Throughout these notes \(S_t\) denotes a random element of the finite state space \(E\) and \(Y_t\) a random element of the observation space \(\mathcal{Y}\).

Two pieces of notation recur. For \(1 \le s \le t\) we write \(Y_{s:t} = (Y_s, Y_{s+1}, \dots, Y_t)\) for a contiguous block, and we write \(f_i\) for the density of the observation distribution in state \(i\) with respect to a fixed dominating measure. Taking counting measure recovers discrete emissions and Lebesgue measure recovers continuous ones, so a single set of formulas covers both. The full notation table is in Appendix A.

1.2 Conditional expectation

Conditioning on a \(\sigma\)-algebra rather than on an event is what makes the zero-probability problem disappear.

Definition 1.3 (Conditional expectation) Let \(X\) be integrable and let \(\mathcal{G} \subseteq \mathcal{F}\) be a sub-\(\sigma\)-algebra. A conditional expectation of \(X\) given \(\mathcal{G}\) is any \(\mathcal{G}\)-measurable integrable random variable \(Z\) satisfying \[ \int_G Z \, d\mathbb{P} = \int_G X \, d\mathbb{P} \qquad \text{for every } G \in \mathcal{G} . \] We write \(Z = \mathbb{E}[X \mid \mathcal{G}]\).

Existence follows from the Radon–Nikodym theorem, and any two versions agree almost surely, so \(\mathbb{E}[X \mid \mathcal{G}]\) is well defined up to null sets. Read the defining property as: \(\mathbb{E}[X \mid \mathcal{G}]\) is the best guess at \(X\) using only information in \(\mathcal{G}\), in the sense that it has the same integral as \(X\) over every \(\mathcal{G}\)-event. When \(X\) is square integrable this is literally an orthogonal projection of \(X\) onto \(L^2(\Omega, \mathcal{G}, \mathbb{P})\).

The following properties are used so often in later derivations that it is worth naming them once.

Proposition 1.1 (Rules for conditional expectation) Let \(X, Y\) be integrable and \(\mathcal{H} \subseteq \mathcal{G} \subseteq \mathcal{F}\).

1. Linearity. \(\mathbb{E}[aX + bY \mid \mathcal{G}] = a \, \mathbb{E}[X \mid \mathcal{G}] + b \, \mathbb{E}[Y \mid \mathcal{G}]\) almost surely.
2. Tower property. \(\mathbb{E}\bigl[ \mathbb{E}[X \mid \mathcal{G}] \bigm| \mathcal{H} \bigr] = \mathbb{E}[X \mid \mathcal{H}]\) almost surely.
3. Taking out what is known. If \(Z\) is \(\mathcal{G}\)-measurable and \(ZX\) is integrable, then \(\mathbb{E}[ZX \mid \mathcal{G}] = Z \, \mathbb{E}[X \mid \mathcal{G}]\) almost surely.
4. Independence. If \(\sigma(X)\) is independent of \(\mathcal{G}\) then \(\mathbb{E}[X \mid \mathcal{G}] = \mathbb{E}[X]\) almost surely.

Proofs are in Williams (1991, ch. 9). Every recursion in Chapter 5 is an application of the tower property combined with the conditional independence structure of the model: the forward recursion conditions on \(S_t\) and then integrates it out, the backward recursion does the same in reverse time.

Filtering and smoothing are conditional expectations. Writing \(\mathcal{Y}_t = \sigma(Y_1, \dots, Y_t)\) for the \(\sigma\)-algebra generated by the observations up to time \(t\), the filtering probability is \[ \mathbb{P}(S_t = i \mid \mathcal{Y}_t) = \mathbb{E}\bigl[ \mathbf{1}\{S_t = i\} \bigm| \mathcal{Y}_t \bigr], \] and smoothing replaces \(\mathcal{Y}_t\) by \(\mathcal{Y}_T\). The forward and backward algorithms are nothing more than efficient ways of evaluating these objects.

1.3 Conditional distributions and Markov kernels

Conditional expectation gives a number for each fixed function. To speak of the conditional distribution of one variable given another, we need those numbers to fit together into a probability measure.

Definition 1.4 (Markov kernel) Let \((S, \mathcal{S})\) and \((T, \mathcal{T})\) be measurable spaces. A Markov kernel from \(S\) to \(T\) is a map \(Q \colon S \times \mathcal{T} \to [0,1]\) such that \(Q(x, \cdot)\) is a probability measure on \(\mathcal{T}\) for each \(x \in S\), and \(x \mapsto Q(x, B)\) is \(\mathcal{S}\)-measurable for each \(B \in \mathcal{T}\).

Definition 1.5 (Regular conditional distribution) Let \(X\) and \(Y\) be random elements of \((S,\mathcal{S})\) and \((T,\mathcal{T})\). A regular conditional distribution of \(X\) given \(Y\) is a Markov kernel \(Q\) from \(T\) to \(S\) with \[ \mathbb{P}(X \in A, \, Y \in B) = \int_B Q(y, A) \, \mathbb{P}_Y(dy) \qquad \text{for all } A \in \mathcal{S},\ B \in \mathcal{T} . \]

Theorem 1.1 (Existence on standard Borel spaces) If \((S, \mathcal{S})\) is a standard Borel space — a Polish space with its Borel \(\sigma\)-algebra — then a regular conditional distribution of \(X\) given \(Y\) exists and is unique up to \(\mathbb{P}_Y\)-null sets.

See Kallenberg (2021, ch. 8) for the proof. Every state and observation space in these notes is standard Borel: finite sets, \(\mathbb{R}^d\), and countable products of these all qualify. So expressions such as \(\mathbb{P}(S_t = i \mid Y_{1:T} = y_{1:T})\) denote a genuine object rather than a formal manipulation, and the freedom to choose a version explains the “for almost every \(y\)” qualifiers that appear in careful statements of the smoothing recursions.

Kernels also give the cleanest statement of the model itself. A finite-state HMM is a Markov kernel \(\boldsymbol{\Gamma}\) from \(E\) to \(E\) together with a kernel from \(E\) to \(\mathcal{Y}\); when \(E\) is finite the first is a matrix, and Chapter 12 replaces it by a genuine kernel to get continuous-state models.

1.4 Modes of convergence

Asymptotic statements in Chapter 8 distinguish three notions.

Definition 1.6 (Almost sure, in probability, in \(L^p\)) For random variables \(X_n, X\) on a common space:

• \(X_n \to X\) almost surely if \(\mathbb{P}(X_n \to X) = 1\);
• \(X_n \to X\) in probability if \(\mathbb{P}(|X_n - X| > \varepsilon) \to 0\) for every \(\varepsilon > 0\);
• \(X_n \to X\) in \(L^p\) (\(p \ge 1\)) if \(\mathbb{E}|X_n - X|^p \to 0\).

Almost sure convergence and \(L^p\) convergence each imply convergence in probability, which in turn implies convergence in distribution; no other implication holds in general. The relevance to HMMs is direct. Consistency of the maximum likelihood estimator is an almost sure statement about the normalised log-likelihood \(T^{-1} \ell_T(\theta)\), proved by an ergodic theorem. Asymptotic normality is a statement about convergence in distribution of \(T^{-1/2}\) times the score, proved by a martingale central limit theorem. The two arguments have different shapes and are kept apart in Chapter 8.

1.5 The simplex and stochastic matrices

1.5.1 Probability vectors

Definition 1.7 (Probability simplex) For \(K \ge 1\), the probability simplex is \[ \Delta^{K-1} = \Bigl\{ \boldsymbol{\mu} = (\mu_1,\dots,\mu_K)^\top \in \mathbb{R}^K : \mu_i \ge 0, \ \textstyle\sum_{i=1}^K \mu_i = 1 \Bigr\} . \]

It is a compact convex set of dimension \(K-1\). Two distances on it matter. The \(\ell^1\) distance \(\lVert \mu - \nu \rVert_1 = \sum_i |\mu_i - \nu_i|\) equals twice the total variation distance and is the natural metric for mixing results. The \(\ell^2\) distance is more convenient when spectral decompositions are in play. On a finite space these are equivalent up to a factor of \(\sqrt{K}\), so the choice is one of convenience rather than substance.

1.5.2 Stochastic matrices

Definition 1.8 (Row-stochastic matrix) A matrix \(\boldsymbol{\Gamma} = (\gamma_{ij}) \in \mathbb{R}^{K \times K}\) is row-stochastic if \(\gamma_{ij} \ge 0\) for all \(i,j\) and \(\sum_{j=1}^K \gamma_{ij} = 1\) for every \(i\).

Equivalently \(\boldsymbol{\Gamma} \mathbf{1} = \mathbf{1}\), where \(\mathbf{1}\) is the all-ones column vector. Row-stochastic matrices are exactly the Markov kernels on a \(K\)-point set: \(\gamma_{ij}\) is the probability of moving to \(j\) from \(i\). If \(\boldsymbol{\mu} \in \Delta^{K-1}\) is the law of \(S_t\), then \(\boldsymbol{\mu}^\top \boldsymbol{\Gamma}\) is the law of \(S_{t+1}\), so the matrix acts on row vectors from the right. This convention follows Zucchini et al. (2016) and is used throughout.

Products of row-stochastic matrices are row-stochastic, which is why the \(n\)-step transition matrix in Chapter 2 is simply \(\boldsymbol{\Gamma}^n\).

1.6 Perron–Frobenius theory and the spectral gap

How fast a Markov chain forgets its initial condition is a spectral question about \(\boldsymbol{\Gamma}\).

Definition 1.9 (Irreducible and primitive matrices) A non-negative matrix \(A \in \mathbb{R}^{K \times K}\) is irreducible if for every pair \((i,j)\) there is \(n \ge 1\) with \((A^n)_{ij} > 0\). It is primitive if there is a single \(n \ge 1\) with \((A^n)_{ij} > 0\) for all \(i,j\) simultaneously.

Theorem 1.2 (Perron–Frobenius) Let \(A\) be a non-negative irreducible \(K \times K\) matrix with spectral radius \(\rho(A)\). Then \(\rho(A)\) is a positive eigenvalue of \(A\); it is algebraically simple; and it admits left and right eigenvectors with strictly positive entries. Up to scaling these are the only non-negative eigenvectors of \(A\). If \(A\) is primitive, every other eigenvalue \(\lambda\) satisfies \(|\lambda| < \rho(A)\).

Horn and Johnson (2013, ch. 8) and Seneta (2006) give proofs. Applied to a row-stochastic \(\boldsymbol{\Gamma}\), the identity \(\boldsymbol{\Gamma}\mathbf{1} = \mathbf{1}\) shows \(1\) is an eigenvalue with positive right eigenvector, so \(\rho(\boldsymbol{\Gamma}) = 1\). Irreducibility then makes it simple, and the corresponding left eigenvector normalised to sum to one is the unique stationary distribution \(\boldsymbol{\pi}\): \[ \boldsymbol{\pi}^\top \boldsymbol{\Gamma} = \boldsymbol{\pi}^\top, \qquad \boldsymbol{\pi} \in \Delta^{K-1} . \] Primitivity — equivalently, irreducibility together with aperiodicity in the language of Chapter 2 — pushes every other eigenvalue strictly inside the unit disc, and that gap is what drives convergence.

Definition 1.10 (Spectral gap) Order the eigenvalues of \(\boldsymbol{\Gamma}\) so that \(1 = \lambda_1\) and \(|\lambda_2| \ge |\lambda_3| \ge \dots \ge |\lambda_K|\). The absolute spectral gap is \(\varrho = 1 - |\lambda_2|\).

Proposition 1.2 (Geometric convergence) Suppose \(\boldsymbol{\Gamma}\) is primitive and diagonalisable with stationary distribution \(\boldsymbol{\pi}\). There is a constant \(C\), depending on the eigenvector matrix but not on \(t\), such that for every \(\boldsymbol{\mu}_0 \in \Delta^{K-1}\), \[ \bigl\lVert \boldsymbol{\mu}_0^\top \boldsymbol{\Gamma}^t - \boldsymbol{\pi}^\top \bigr\rVert_2 \;\le\; C \, |\lambda_2|^t . \]

Proof. Write the spectral decomposition \(\boldsymbol{\Gamma} = \sum_{k=1}^K \lambda_k \, v_k u_k^\top\) with \(u_k^\top v_l = \delta_{kl}\), ordered so that \(\lambda_1 = 1\), \(v_1 = \mathbf{1}\) and \(u_1 = \boldsymbol{\pi}\). Then \(\boldsymbol{\Gamma}^t = \mathbf{1}\boldsymbol{\pi}^\top + \sum_{k \ge 2} \lambda_k^t \, v_k u_k^\top\). Since \(\boldsymbol{\mu}_0^\top \mathbf{1} = 1\), the leading term contributes exactly \(\boldsymbol{\pi}^\top\), and the remainder is bounded in norm by \(|\lambda_2|^t \sum_{k \ge 2} \lVert v_k \rVert_2 \lVert u_k \rVert_2\).

Diagonalisability is a convenience, not a necessity; the Jordan form gives the same conclusion with an extra polynomial factor. The reversible case in Chapter 2 is cleaner still, because self-adjointness in \(L^2(\boldsymbol{\pi})\) makes the spectrum real and the eigenvector basis orthonormal, so \(C\) can be computed explicitly.

1.7 Convexity, entropy and Kullback–Leibler divergence

1.7.1 Convex functions on the simplex

Definition 1.11 (Convexity) A function \(f \colon \Delta^{K-1} \to \mathbb{R}\) is convex if \(f(\theta \mu + (1-\theta)\nu) \le \theta f(\mu) + (1-\theta) f(\nu)\) for all \(\mu, \nu \in \Delta^{K-1}\) and \(\theta \in [0,1]\), and strictly convex if the inequality is strict whenever \(\mu \ne \nu\) and \(\theta \in (0,1)\).

Two functionals do most of the work. The Shannon entropy \(H(\mu) = -\sum_i \mu_i \log \mu_i\) is strictly concave on \(\Delta^{K-1}\), and the negative entropy \(\phi(\mu) = \sum_i \mu_i \log \mu_i\) is therefore strictly convex.

1.7.2 Kullback–Leibler divergence

Definition 1.12 (Kullback–Leibler divergence) For \(p, q \in \Delta^{K-1}\) with \(q_i > 0\) whenever \(p_i > 0\), \[ \mathrm{KL}(p \Vert q) = \sum_{i=1}^K p_i \log \frac{p_i}{q_i}, \] with the convention \(0 \log 0 = 0\). For measures \(P \ll Q\) on a general space, \(\mathrm{KL}(P \Vert Q) = \int \log \frac{dP}{dQ} \, dP\).

Proposition 1.3 (KL divergence is a Bregman divergence) Let \(\phi(p) = \sum_i p_i \log p_i\) on the relative interior of \(\Delta^{K-1}\) and define the Bregman divergence \[ D_\phi(p, q) = \phi(p) - \phi(q) - \langle \nabla \phi(q), \, p - q \rangle . \] Then \(D_\phi(p,q) = \mathrm{KL}(p \Vert q)\). Consequently \(\mathrm{KL}(p \Vert q) \ge 0\), with equality if and only if \(p = q\).

Proof. Since \(\partial \phi / \partial q_i = \log q_i + 1\), \[ D_\phi(p,q) = \sum_i p_i \log p_i - \sum_i q_i \log q_i - \sum_i (\log q_i + 1)(p_i - q_i). \] The terms \(\sum_i (p_i - q_i)\) vanish because both vectors sum to one, and the remaining terms collapse to \(\sum_i p_i \log p_i - \sum_i p_i \log q_i = \mathrm{KL}(p \Vert q)\). Non-negativity and the equality case follow from strict convexity of \(\phi\), since a Bregman divergence is the gap between a strictly convex function and its tangent plane.

Non-negativity of KL divergence is the single fact behind the monotonicity of EM (Chapter 6), the variational bound of Chapter 7, and the identification of the pseudo-true parameter under misspecification (Chapter 8). Note that KL is not symmetric and does not satisfy a triangle inequality, so it is not a metric; the asymmetry is exactly why forward and reverse KL give different variational approximations.

1.7.3 Exponential families and convex duality

Definition 1.13 (Exponential family) A family of densities with respect to a dominating measure \(\nu\) is an exponential family in natural form if \[ f(y ; \eta) = h(y) \exp\bigl\{ \langle \eta, \, T(y) \rangle - A(\eta) \bigr\}, \qquad A(\eta) = \log \int h(y) e^{\langle \eta, T(y)\rangle} \, \nu(dy), \] where \(T\) is the sufficient statistic, \(\eta\) the natural parameter, and \(A\) the log-partition function.

The log-partition function is convex, and on the interior of the natural parameter space it is smooth with \(\nabla A(\eta) = \mathbb{E}_\eta[T(Y)]\) and \(\nabla^2 A(\eta) = \operatorname{Var}_\eta(T(Y))\). Its convex conjugate \[ A^*(m) = \sup_{\eta} \bigl\{ \langle \eta, m \rangle - A(\eta) \bigr\} \] is the negative entropy expressed in mean parameters, which is the general form of the pairing seen above for the finite simplex, where \(\phi(p) = \sum_i p_i \log p_i\) and \(\phi^*(\eta) = \log \sum_i e^{\eta_i}\).

Two consequences shape later chapters. Because \(\nabla A\) maps natural to mean parameters bijectively on the interior, maximising an exponential-family likelihood amounts to moment matching, and the M-step of EM in Chapter 6 reduces to setting expected sufficient statistics equal to weighted empirical ones. Because \(A\) and \(A^*\) are conjugate, entropy-regularised problems of the form \[ \max_{q} \, \bigl\{ \mathbb{E}_q[\log p(Y,S)] + H(q) \bigr\} \] have exponential-family solutions, which is the starting point for the variational treatment in Wainwright and Jordan (2008). The log-sum-exp expressions that appear all over the numerical implementations of Chapter 7 are the finite-dimensional instance of \(A\).

Check your understanding. Why does the theory need regular conditional distributions rather than just conditional expectations, given that everything in a finite-state HMM is discrete?

TipShow answer

The states are discrete but the observations usually are not. Writing \(\mathbb{P}(S_t = i \mid Y_{1:T} = y_{1:T})\) conditions on an event of probability zero whenever \(Y\) has a continuous distribution, so the elementary definition divides by zero.

Conditional expectation given the \(\sigma\)-algebra \(\sigma(Y_{1:T})\) is well defined, but it produces a number for each fixed function, not a probability measure. Theorem 1.1 supplies the measure, and it is what makes the smoothing distribution a genuine object rather than a formal manipulation. The “for almost every \(y\)” qualifiers in careful statements of the recursions are the price.

1.8 Summary

The chapter has assembled four things:

• conditional expectation and regular conditional distributions, which make filtering and smoothing well-defined objects rather than notation;
• Markov kernels, which give a single description of the transition and emission mechanisms that survives the move from finite to continuous state spaces;
• Perron–Frobenius theory and the spectral gap, which quantify how fast a chain forgets its initial distribution;
• convexity, KL divergence and exponential families, which underlie EM, variational bounds, and the identification arguments in the asymptotic theory.

1.9 Further reading

Williams (1991) is the shortest rigorous route to conditional expectation and martingales; Kallenberg (2021, ch. 8) covers regular conditional distributions and kernels in full generality. For non-negative matrices, Seneta (2006) is written with Markov chains in mind and Horn and Johnson (2013, ch. 8) gives the general spectral theory. Boyd and Vandenberghe (2004) covers convex duality at the level used here, and Amari (2016) develops the information-geometric picture of exponential families. Cappé et al. (2005, ch. 1) sets up HMMs in exactly this measure-theoretic language and is the natural companion to this chapter.

Amari, Shun-ichi. 2016. Information Geometry and Its Applications. Springer. https://doi.org/10.1007/978-4-431-55978-8.

Boyd, Stephen, and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press. https://doi.org/10.1017/CBO9780511804441.

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.

Horn, Roger A., and Charles R. Johnson. 2013. Matrix Analysis. 2nd ed. Cambridge University Press. https://doi.org/10.1017/CBO9780511810817.

Kallenberg, Olav. 2021. Foundations of Modern Probability. 3rd ed. Springer. https://doi.org/10.1007/978-3-030-61871-1.

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

Wainwright, Martin J., and Michael I. Jordan. 2008. “Graphical Models, Exponential Families, and Variational Inference.” Foundations and Trends in Machine Learning 1 (1–2): 1–305. https://doi.org/10.1561/2200000001.

Williams, David. 1991. Probability with Martingales. Cambridge University Press. https://doi.org/10.1017/CBO9780511813658.

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.