Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V
Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IX
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 What Is a Hidden Markov Model? . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Beyond Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Finite Hidden Markov Models. . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Normal Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . 13
1.3.3 Gaussian Linear State-Space Models . . . . . . . . . . . . . . . . . 15
1.3.4 Conditionally Gaussian Linear State-Space Models . . . . 17
1.3.5 General (Continuous) State-Space HMMs . . . . . . . . . . . . 24
1.3.6 Switching Processes with Markov Regime. . . . . . . . . . . . . 29
1.4 Left-to-Right and Ergodic Hidden Markov Models . . . . . . . . . . . 33
2 Main Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1.1 Transition Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1.2 Homogeneous Markov Chains . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.3 Non-homogeneous Markov Chains . . . . . . . . . . . . . . . . . . . 40
2.2 Hidden Markov Models. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.1 Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.2.2 Conditional Independence in Hidden Markov Models . . . 44
2.2.3 Hierarchical Hidden Markov Models . . . . . . . . . . . . . . . . . 46
Part I State Inference
XII Contents
3 Filtering and Smoothing Recursions . . . . . . . . . . . . . . . . . . . . . . . 51
3.1 Basic Notations and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.1 Likelihood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.2 Smoothing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.1.3 The Forward-Backward Decomposition . . . . . . . . . . . . . . . 56
3.1.4 Implicit Conditioning (Please Read This Section!) . . . . . 58
3.2 Forward-Backward. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2.1 The Forward-Backward Recursions . . . . . . . . . . . . . . . . . . 59
3.2.2 Filtering and Normalized Recursion . . . . . . . . . . . . . . . . . . 61
3.3 Markovian Decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.1 Forward Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.2 Backward Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.4 Complements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4 Advanced Topics in Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.1 Recursive Computation of Smoothed Functionals . . . . . . . . . . . . 77
4.1.1 Fixed Point Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.1.2 Recursive Smoothers for General Functionals . . . . . . . . . 79
4.1.3 Comparison with Forward-Backward Smoothing . . . . . . . 82
4.2 Filtering and Smoothing in More General Models . . . . . . . . . . . . 85
4.2.1 Smoothing in Markov-switching Models . . . . . . . . . . . . . . 86
4.2.2 Smoothing in Partially Observed Markov Chains . . . . . . 86
4.2.3 Marginal Smoothing in Hierarchical HMMs . . . . . . . . . . . 87
4.3 Forgetting of the Initial Condition . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.3.1 Total Variation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.3.2 Lip*****z Contraction for Transition Kernels . . . . . . . . . . . 95
4.3.3 The Doeblin Condition and Uniform Ergodicity . . . . . . . 97
4.3.4 Forgetting Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.3.5 Uniform Forgetting Under Strong Mixing Conditions . . . 105
4.3.6 Forgetting Under Alternative Conditions . . . . . . . . . . . . . 110
5 Applications of Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.1 Models with Finite State Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.1.1 Smoothing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.1.2 Maximum a Posteriori Sequence Estimation . . . . . . . . . . 125
5.2 Gaussian Linear State-Space Models . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.1 Filtering and Backward Markovian Smoothing . . . . . . . . 127
5.2.2 Linear Prediction Interpretation . . . . . . . . . . . . . . . . . . . . . 131
5.2.3 The Prediction and Filtering