Contents

Preface to the Second Edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

Part I Introduction

1 Hidden Markov Model Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1 Models, Objectives, and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Book Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Part II Discrete-Time HMM Estimation

2 Discrete States and Discrete Observations . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 Change of Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4 Unnormalized Estimates and Bayes’ Formula . . . . . . . . . . . . . . . . . . . 26

2.5 A General Unnormalized Recursive Filter . . . . . . . . . . . . . . . . . . . . . . 28

2.6 States, Transitions, and Occupation Times . . . . . . . . . . . . . . . . . . . . . . 30

2.7 Parameter Reestimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.8 Recursive Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.9 Quantized Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.10 The Dependent Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.11 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3 Continuous-Range Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.2 State and Observation Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.3 Conditional Expectations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.4 Change of Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.5 Filter-Based State Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.6 Smoother-Based State Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.7 Vector Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3.8 Recursive Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.9 HMMs with Colored Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3.10 Mixed-State HMMEstimation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.11 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4 Continuous-Range States and Observations . . . . . . . . . . . . . . . . . . . . . . . 83

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.2 Linear Dynamics and Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.3 The ARMAX Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

4.4 Nonlinear Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

4.5 Kalman Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4.6 State and Mode Estimation for Discrete-Time Jump Markov

Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

4.7 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

4.8 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

5 A General Recursive Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

5.2 Signal and Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

5.3 Change of Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

5.4 Recursive Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

5.5 Extended Kalman Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

5.6 Parameter Identification and Tracking . . . . . . . . . . . . . . . . . . . . . . . . . 149

5.7 Formulation in Terms of Transition Densities . . . . . . . . . . . . . . . . . . . 153

5.8 Dependent Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

5.9 Recursive Prediction Error Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 159

5.10 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

6 Practical Recursive Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

6.2 Recursive Prediction Error HMM Algorithm . . . . . . . . . . . . . . . . . . . . 166

6.3 Example: Quadrature Amplitude Modulation . . . . . . . . . . . . . . . . . . . 171

6.4 Example: Frequency Modulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

6.5 Coupled-Conditional Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

6.6 Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

Part III Continuous-Time HMM Estimation

7 Discrete-Range States and Observations . . . . . . . . . . . . . . . . . . . . . . . . . . 197

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

7.2 Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

7.3 A General Finite-Dimensional Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

7.4 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

7.5 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

8 Markov Chains in Brownian Motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

8.2 The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

8.3 A General Finite-Dimensional Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

8.4 States, Transitions, and Occupation Times . . . . . . . . . . . . . . . . . . . . . . 216

8.5 Parameter Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

8.6 Finite-Dimensional Predictors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

8.7 A Non-Markov Finite-Dimensional Filter . . . . . . . . . . . . . . . . . . . . . . 225

8.8 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

Part IV Two-Dimensional HMM Estimation

9 Hidden Markov Random Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

9.1 Discrete Signal and Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

9.2 HMRF Observed in Gaussian Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

9.3 Continuous-State HMRF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

9.4 Example: AMixed HMRF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

9.5 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

Part V HMM Optimal Control

10 Discrete-Time HMM Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

10.1 Control of Finite-State Processes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273

10.2 More General Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

10.3 A Dependent Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

10.4 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

11 Risk-Sensitive Control of HMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

11.2 The Risk-Sensitive Control Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

11.3 Connection with H∞ Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

11.4 Connection with H2 or Risk-Neutral Control . . . . . . . . . . . . . . . . . . . . 299

11.5 A Finite-Dimensional Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

11.6 Risk-Sensitive LQG Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

11.7 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

12 Continuous-Time HMM Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

12.2 Robust Control of a Partially Observed Markov Chain . . . . . . . . . . . . 315

12.3 The Dependent Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

12.4 Hybrid Conditionally Linear Process . . . . . . . . . . . . . . . . . . . . . . . . . . 340

12.5 Problems and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

A Basic Probability Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

B Continuous-Time Martingale Representation . . . . . . . . . . . . . . . . . . . . . . 359

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373

Subject Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375