15  Exercises

The exercises below are proof-based and grouped by the chapter they follow. Difficulty is marked: (*) routine given the chapter, (**) requires assembling several results, (***) open-ended or research-adjacent. No solutions are provided.

Exercises marked with a computer icon call for implementation. Anything that can be implemented should be, since the invariants of Chapter 7 make HMM code unusually easy to check.

15.1 Probability and Markov chains

Exercise 15.1 (Conditional expectation (*)) Let \(X\) be integrable on \((\Omega,\mathcal{F},\mathbb{P})\) and \(\mathcal{G} \subseteq \mathcal{F}\) a sub-\(\sigma\)-algebra.

  1. Show any two versions of \(\mathbb{E}[X \mid \mathcal{G}]\) agree almost surely.

  2. Prove the tower property (Proposition 1.1, part 2) from the defining property alone.

  3. Show that if \(X \in L^2\), then \(\mathbb{E}[X \mid \mathcal{G}]\) is the orthogonal projection of \(X\) onto \(L^2(\Omega,\mathcal{G},\mathbb{P})\), and deduce \(\operatorname{Var}(X) = \mathbb{E}[\operatorname{Var}(X \mid \mathcal{G})] + \operatorname{Var}(\mathbb{E}[X \mid \mathcal{G}])\).

Exercise 15.2 (Stochastic matrices and their spectra (**))  

  1. Show that every eigenvalue \(\lambda\) of a row-stochastic matrix satisfies \(|\lambda| \le 1\).

  2. Give a \(3\times3\) irreducible stochastic matrix with an eigenvalue of modulus \(1\) other than \(1\) itself. What is its period?

  3. Show that a stochastic matrix with all entries strictly positive is primitive, and bound \(|\lambda_2|\) in terms of \(\min_{ij}\gamma_{ij}\).

Exercise 15.3 (The ergodic theorem (**)) Prove Theorem 2.2 for an irreducible finite-state chain, using the regeneration structure at returns to a fixed state. Where exactly does the argument require finiteness of the state space, and where does it require irreducibility? Show by example that the conclusion can fail without irreducibility.

Exercise 15.4 (Dobrushin’s coefficient (**))  

  1. Prove Theorem 2.3: \(\lVert \mu^\top\boldsymbol{\Gamma} - \nu^\top\boldsymbol{\Gamma}\rVert_{\mathrm{TV}} \le \kappa(\boldsymbol{\Gamma})\lVert\mu-\nu\rVert_{\mathrm{TV}}\).

  2. Prove submultiplicativity, \(\kappa(\boldsymbol{\Gamma}_1\boldsymbol{\Gamma}_2) \le \kappa(\boldsymbol{\Gamma}_1)\kappa(\boldsymbol{\Gamma}_2)\).

  3. Show the Doeblin condition \(\gamma_{ij} \ge \epsilon\nu_j\) implies \(\kappa(\boldsymbol{\Gamma}) \le 1-\epsilon\).

  4. Compare the bound from (c) with the spectral bound of Proposition 2.5 for a two-state chain with \(\gamma_{12} = \gamma_{21} = p\). Which is sharper, and for which values of \(p\)?

Exercise 15.5 (KL divergence (*))  

  1. Verify Proposition 1.3 by direct computation.

  2. Show KL is jointly convex in \((p,q)\).

  3. Give an example with \(\mathrm{KL}(p\Vert q) \ne \mathrm{KL}(q \Vert p)\) and one where the triangle inequality fails, confirming KL is not a metric.

15.2 Model structure and likelihood

Exercise 15.6 (Conditional independence (*))  

  1. Prove Theorem 3.1 from assumptions (A1) and (A2), being explicit about where each is used.

  2. Prove parts 1 and 4 of Proposition 3.1.

  3. Give a counterexample showing \(Y_1\) and \(Y_2\) are not in general independent, and compute \(\operatorname{Cov}(Y_1,Y_2)\) for a two-state HMM with Gaussian emissions in terms of \(\boldsymbol{\pi}\), \(\boldsymbol{\Gamma}\) and the state means.

Exercise 15.7 (Matrix representation (*))  

  1. Prove Theorem 3.2 by induction on \(T\).

  2. Show that if \(\boldsymbol{\delta} = \boldsymbol{\pi}\) then \(L_T\) is invariant under time reversal in the sense that reversing \(y_{1:T}\) and replacing \(\boldsymbol{\Gamma}\) by the time-reversed matrix \(\tilde\gamma_{ij} = \pi_j\gamma_{ji}/\pi_i\) leaves the likelihood unchanged.

  3. Deduce that a reversible hidden chain gives a time-reversible observed process, and explain why the converse fails.

Exercise 15.8 (What HMMs can represent (**)) Consider a stationary two-state HMM with Poisson emissions, means \(\lambda_1 \ne \lambda_2\).

  1. Compute the marginal distribution of \(Y_t\) and show it is overdispersed relative to a Poisson with the same mean.

  2. Compute the autocorrelation function of \((Y_t)\) and show it decays geometrically at rate \(\lambda_2(\boldsymbol{\Gamma})\), the second eigenvalue.

  3. Deduce which autocorrelation functions a two-state Poisson HMM can and cannot produce. Can it produce a negative lag-1 autocorrelation?

15.3 Inference algorithms

Exercise 15.9 (Forward and backward recursions (*))  

  1. Prove Theorem 5.1 by induction, stating where each model assumption enters.

  2. Prove Theorem 5.3.

  3. Prove Proposition 5.2 and verify the marginal consistency conditions stated there.

Exercise 15.10 (Scaling (*))  

  1. Prove Proposition 5.1: the scale factors are the one-step predictive densities and their logarithms sum to \(\ell_T\).

  2. Show the synchronised backward scaling of Chapter 5 gives \(\gamma_t(i) = \hat\alpha_t(i)\hat\beta_t(i)\) exactly.

  3. 💻 Implement the forward algorithm in both scaled and log-domain form. Verify agreement to machine precision on a test problem, then find a model where the unscaled version underflows and confirm both scaled versions still work.

Exercise 15.11 (Viterbi (**))  

  1. Prove Theorem 5.5, stating the optimal substructure property precisely and showing the recursion computes it.

  2. Construct an explicit two-state HMM and an observation sequence of length at most \(5\) for which the sequence of marginal modes differs from the Viterbi path. Give the numbers.

  3. Construct an example where the sequence of marginal modes has probability zero under the model.

  4. Generalise the recursion to return the \(n\) best paths. What is the complexity?

Exercise 15.12 (The semiring view (**)) Both the forward algorithm and Viterbi have the form \(v_t(j) = f_j(y_t) \otimes \bigoplus_i \bigl( v_{t-1}(i) \otimes \gamma_{ij} \bigr)\) for a commutative semiring \((\oplus,\otimes)\).

  1. Identify the semiring for each.

  2. What is computed by the semiring \((\max, \min)\)? By \((\oplus,\otimes) = (+,\times)\) over the expectation semiring used to accumulate expected counts?

  3. Show that the posterior entropy \(H(S_{1:T} \mid y_{1:T})\) can be computed in \(\mathcal{O}(K^2T)\) by a suitable choice, and give the recursion.

Exercise 15.13 (Filter stability (**))  

  1. Prove Theorem 5.2 under the Doeblin condition, by showing the filter update map does not increase the Dobrushin coefficient.

  2. 💻 Verify numerically: fit a model, then run the filter from two very different initial distributions on the same data and plot the total variation distance against \(t\) on a log scale. Compare the observed rate with the bound.

  3. Explain why this result makes \(\boldsymbol{\delta}\) hard to estimate from a single long series.

15.4 Estimation

Exercise 15.14 (EM (*))  

  1. Verify identity 6.1.

  2. Prove Theorem 6.1, and identify exactly the conditions under which the inequality is strict.

  3. Prove Proposition 6.2, deriving both closed-form updates by Lagrange multipliers.

  4. Show that the generalised EM algorithm, which only increases \(Q\) rather than maximising it, retains the monotonicity property.

Exercise 15.15 (Fixed points and failure modes (**))  

  1. Show that if two states are initialised with identical emission parameters and identical rows of \(\boldsymbol{\Gamma}\), EM leaves them identical forever. Identify the corresponding point of the likelihood surface.

  2. For a Gaussian HMM with unconstrained variances, show \(\sup_\theta \ell_T(\theta) = +\infty\) and exhibit a sequence attaining it.

  3. 💻 Implement Baum–Welch. On simulated data, run from 100 random starts and tabulate the distribution of the resulting log-likelihoods. How often is the best value found?

Exercise 15.16 (Score and information (**))  

  1. Prove Fisher’s identity (Proposition 6.1).

  2. Write out \(\nabla_\theta \ell_T\) explicitly in terms of \(\gamma_t(i)\) and \(\xi_t(i,j)\) for the transition parameters, and confirm one forward–backward pass suffices.

  3. State Louis’s identity and use it to express the observed information in terms of forward–backward quantities.

Exercise 15.17 (Identifiability (**))  

  1. Prove Proposition 3.2.

  2. Show that if two states have identical emission distributions and identical rows of \(\boldsymbol{\Gamma}\), the parameter is not identified, and describe the resulting non-identified set.

  3. Construct two parameter values, not related by permutation, inducing the same law for \(Y_{1:T}\) for all \(T\). Which hypothesis of Theorem 4.1 fails?

  4. (***) Read Allman et al. (2009) and reconstruct the tensor argument behind Theorem 4.1, stating Kruskal’s condition and verifying it in the HMM setting.

15.5 Asymptotics

Exercise 15.18 (The limiting log-likelihood (***))  

  1. Explain why \(T^{-1}\ell_T(\theta)\) is not an average of stationary terms, and why the infinite-past construction of Theorem 8.1 repairs this.

  2. Show that under the Doeblin condition the approximation error from replacing the finite past by the infinite past decays geometrically, and that the errors are summable.

  3. (***) Read Leroux (1992) and reconstruct the subadditive ergodic theorem argument. Compare with the forgetting-based proof.

Exercise 15.19 (Consistency and normality (**))  

  1. Prove the information inequality in Theorem 8.2 and identify the equality case.

  2. Complete the Wald-style argument, stating where compactness and uniform convergence are used.

  3. Show the score is a martingale with respect to the observation filtration, and explain why this makes a martingale CLT the natural tool.

  4. Explain what goes wrong when \(\theta^\star\) lies on the boundary of \(\Theta\), and describe the limiting distribution in a simple two-state example where one transition probability is zero.

Exercise 15.20 (Number of states (**))  

  1. Describe precisely the two ways in which a \(K\)-state HMM is embedded in a \((K+1)\)-state model, and show the parameter is not identified at either.

  2. Explain why the likelihood ratio statistic does not have a \(\chi^2\) limit.

  3. 💻 Simulate from a three-state model and fit \(K = 1,\dots,6\). Tabulate AIC and BIC over many replications and report how often each selects the truth.

15.6 Bayesian, hierarchical and telescoping

Exercise 15.21 (Forward filtering, backward sampling (*))  

  1. Prove Theorem 9.1, identifying which conditional independence is used at each step.

  2. Explain why single-site Gibbs updating of the states mixes badly, and estimate how the mixing time scales with \(T\) for a highly persistent chain.

  3. 💻 Implement FFBS and verify it by comparing the empirical frequency of sampled state sequences with exact smoothed probabilities on a short series where enumeration is feasible.

Exercise 15.22 (Label switching in MCMC (**))  

  1. Show that if both likelihood and prior are permutation-invariant, then so is the posterior, and deduce that all marginal posteriors of \(\phi_i\) coincide.

  2. Explain why a chain producing clean unimodal state-specific posteriors may indicate poor mixing.

  3. Give three permutation-invariant functionals of the posterior that can be reported without relabelling.

  4. 💻 Run the sampler of Definition 9.2 with and without random permutation of labels after each sweep, and compare the resulting marginal posteriors.

Exercise 15.23 (Multilevel HMMs (**))  

  1. Write out the full hierarchical model for \(N\) series with random effects on the transition logits, and give the complete-data likelihood.

  2. Derive the conditional posterior of the random effects given the states and hyperparameters. Is it conjugate?

  3. Explain the funnel geometry that arises when the group-level variance is small, and show how the non-centred parameterisation removes it.

  4. Show that as the group-level variance tends to zero and to infinity, the model recovers complete pooling and no pooling respectively.

Exercise 15.24 (The telescoping sampler (**))  

  1. Prove Proposition 11.1.

  2. Prove Proposition 11.2, explaining carefully where the falling factorial comes from.

  3. Derive Theorem 11.1, and verify that the parameters of empty components genuinely drop out.

  4. Show that under the dynamic specification \(\gamma_K = \alpha/K\), the total Dirichlet mass is constant in \(K\), and describe the effect on the prior for \(K_+\).

Exercise 15.25 (Telescoping for HMMs (***))  

  1. Prove Proposition 11.3, and verify that rows corresponding to unoccupied states contribute a factor of exactly \(1\).

  2. Derive Theorem 11.2 and compare its structure term by term with Theorem 11.1.

  3. Explain the mechanism by which a new state becomes occupied during the FFBS step, and why a diffuse \(G_0\) suppresses it.

  4. 💻 Implement the sampler of Definition 11.4. Simulate from a three-state model and check that the posterior of \(K_+\) concentrates on \(3\). Then vary the prior \(p(K)\) and report how the posteriors of \(K\) and \(K_+\) respond.

  5. (***) Compare against an overfitted model with \(K\) fixed at \(10\) and \(e_0 = 0.1\), in the manner of Rousseau and Mengersen (2011). Which recovers the truth more reliably, and how do the two summaries differ in what they express?

15.7 Extensions and alternative perspectives

Exercise 15.26 (The Kalman filter as a forward algorithm (**))  

  1. Derive Theorem 12.1 from the predict–update recursion.

  2. Show the prediction error decomposition gives \(\ell_T\) as a sum of Gaussian log-densities, and identify the analogue of the scale factors \(c_t\).

  3. State the analogue of FFBS for the linear-Gaussian model, and compare its structure with Theorem 9.1.

Exercise 15.27 (Intractability of switching models (**))  

  1. Show that in Definition 12.4 the exact filtering distribution of \(X_t\) given \(y_{1:t}\) is a mixture of \(K^t\) Gaussians.

  2. Explain why no reorganisation of the recursion avoids this, in contrast with the finite-state case.

  3. Describe the collapsing approximation and state precisely what it preserves.

Exercise 15.28 (Regret bounds (**))  

  1. Prove Proposition 13.1.

  2. Derive the \(\tfrac{d}{2}\log T\) rate by choosing \(A\) to be a ball of radius \(T^{-1/2}\) and computing its prior mass.

  3. Explain the relationship between this term and the penalty in BIC.

  4. Explain precisely why a regret guarantee licenses using an HMM for prediction but not for interpreting its states.

Exercise 15.29 (Belief states (**))  

  1. Prove Theorem 13.1: beliefs form a Markov decision process on the simplex.

  2. Show the belief update is exactly the filtering step of Chapter 5.

  3. Show the finite-horizon value function is piecewise linear and convex in \(b\), and interpret the convexity.

15.8 Using these exercises

A one-semester course can be built as follows.

A twelve-week schedule
Weeks Chapters Exercises
1–2 Chapter 1, Chapter 2 Exercise 15.1 – Exercise 15.5
3–4 Chapter 3, Chapter 4 Exercise 15.6 – Exercise 15.8
5–6 Chapter 5 Exercise 15.9 – Exercise 15.13
7–8 Chapter 6, Chapter 7 Exercise 15.14 – Exercise 15.17
9 Chapter 8 Exercise 15.18 – Exercise 15.20
10–11 Chapter 9, Chapter 10, Chapter 11 Exercise 15.21 – Exercise 15.25
12 Chapter 12, Chapter 13, Chapter 14 Exercise 15.26 – Exercise 15.29

The implementation exercises are worth more than the proofs for most students, and Exercise 15.15 (b) and (c) in particular tend to change how people think about maximum likelihood.