Preface ...................................................... xiii
List of Figures .............................................. xvii
List of Tables ................................................ xix
Notation and Symbols .......................................... xxi
1 Motivation for the Sequential Approach and Selected
Applications ............................................... 1
1.1 Motivation ................................................. 1
1.2 Two Theoretical Tracks ..................................... 2
1.2.1 Track 1: Sequential Hypothesis Testing .............. 2
1.2.2 Track 2: Quickest Changepoint Detection ............. 3
1.3 Several Applications ....................................... 5
1.3.1 Quality Control ..................................... 6
1.3.2 Target Detection and Tracking ....................... 7
1.3.3 Navigation System Integrity Monitoring .............. 7
1.3.4 Signal Processing Applications ...................... 8
1.3.5 Mechanical Systems Integrity Monitoring ............. 9
1.3.6 Finance and Economics ............................... 9
1.3.7 Computer Network Surveillance and Security ......... 10
2 Background on Probability and Statistics .................. 13
2.1 Probability, Expectation, Markov Times, and Stochastic
Processes ................................................. 13
2.1.1 Probability and Expectation ........................ 13
2.1.2 Exponential Family of Distributions ................ 14
2.1.3 Markov Times ....................................... 16
2.1.4 Markov Processes ................................... 17
2.1.5 Brownian Motion and Itô's Stochastic Integral ...... 22
2.1.6 Stochastic Differential Equations, Itô Processes,
and Diffusion Processes ............................ 25
2.1.7 Point Random Processes ............................. 28
2.2 Certain Useful Equalities and Inequalities ................ 29
2.3 Martingales, Optional Stopping, and Wald's Identities ..... 30
2.4 Stochastic Convergence .................................... 33
2.4.1 Standard Modes of Convergence ...................... 33
2.4.2 Complete Convergence ............................... 35
2.4.3 r-Quick Convergence ................................ 36
2.5 Elements of Renewal Theory for Random Walks ............... 38
2.5.1 The Overshoot Problem .............................. 39
2.5.2 Approximating the Distribution of the Overshoot
via Renewal Theoretic Considerations ............... 40
2.5.3 Properties of the Stopping Time Tα ................. 45
2.5.4 On the Joint Distribution of the Stopping Time
and Overshoot ...................................... 48
2.6 Nonlinear Renewal Theory .................................. 49
2.6.1 Preliminaries ...................................... 49
2.6.2 Asymptotic Properties of the Stopping Time and
Overshoot for Perturbed Random Walks ............... 51
2.6.3 The General Case ................................... 57
2.7 Sequential Decision Rules and Optimal Stopping Theory ..... 64
2.7.1 Sequential Decision Rules .......................... 65
2.7.2 Optimal Stopping Rules ............................. 67
2.7.3 Optimal Sequential Decision-Making Rules ........... 71
2.7.4 Non-Bayesian Optimality Criteria: Minimax
Decision Rules ..................................... 79
2.8 Information ............................................... 82
2.8.1 Kullback-Leibler Information ....................... 82
2.8.2 Fisher Information ................................. 83
2.9 Hypothesis Testing: Performance and Optimality Criteria ... 86
2.9.1 Notation and Main Criteria ......................... 87
2.9.2 Testing between Two Simple Hypotheses .............. 90
2.9.3 Composite Hypothesis Testing Problems .............. 94
2.9.4 Bayesian and Minimax Approaches for Two Composite
Hypotheses ......................................... 98
2.9.5 Invariant Tests .................................... 99
2.9.6 Testing between Multiple Simple Hypotheses ........ 101
2.10 Hypothesis Testing: Gaussian Linear Model ................ 104
2.10.1 Uniformly Best Constant Power Test ................ 104
2.10.2 Minimax Test ...................................... 108
2.10.3 The Generalized Likelihood Ratio Test ............. 111
2.11 Hypothesis Testing: Asymptotic Approaches ................ 115
2.11.1 Motivation ........................................ 115
2.11.2 Local Asymptotic Expansion of the Likelihood
Ratio ............................................. 115
2.11.3 The Main Idea of the Asymptotically Optimal
Tests ............................................. 116
2.11.4 Asymptotically Optimal Tests for Two Simple
Hypotheses ........................................ 117
I. Sequential Hypothesis Testing ............................. 119
3 Sequential Hypothesis Testing: Two Simple Hypotheses ..... 121
3.1 Sequential Probability Ratio Test ........................ 121
3.1.1 Wald's Approximations for the Operating
Characteristic and the Expected Sample Size ....... 122
3.1.2 Bounds for the Operating Characteristic and the
Expected Sample Size .............................. 126
3.1.3 Asymptotically Accurate Approximations for the
ОС and the ESS .................................... 128
3.1.4 Integral Equations and Numerical Techniques for
Performance Evaluation ............................ 134
3.1.5 Evaluation of the Operating Characteristics and
Comparison with the Neyman-Pearson Test for the
Gaussian Model .................................... 137
3.1.6 Evaluation of the Operating Characteristics and
Comparison with the Neyman-Pearson Test for the
Exponential Model ................................. 142
3.2 SPRT Optimality in the iid Case .......................... 148
3.2.1 Lower Bounds for the Expected Sample Sizes and
Approximate Optimality ............................ 148
3.2.2 SPRT Optimality in a Bayesian Problem ............. 150
3.2.3 Strong Optimality of the SPRT ..................... 156
3.2.4 Generalization to a Special Non-iid Case .......... 157
3.3 Extended Optimality of the SPRT in the General Non-iid
Case ..................................................... 159
3.4 Asymptotic Optimality of the SPRT in the General
Non-iid Case ............................................. 163
3.4.1 Lower Bounds for Moments of the Stopping Time
and Weak Asymptotic Optimality .................... 164
3.4.2 Asymptotic Optimality of the SPRT with Respect
to Moments of the Stopping Time ................... 166
3.4.3 Detection of a Deterministic Signal in Gaussian
Noise ............................................. 169
3.4.4 Detection of a Gaussian Markov Signal in White
Noise ............................................. 174
3.4.5 Testing for a Nonhomogeneous Poisson Process ...... 176
3.4.6 Testing the Mean of AR Processes .................. 177
3.4.7 Testing the Mean in Linear State-Space Models ..... 180
3.5 SPRT: Local Approach ..................................... 181
3.5.1 ESS Function ...................................... 182
3.5.2 ОС Function ....................................... 182
3.5.3 Locally Most Powerful Sequential Test ............. 183
3.6 Nuisance Parameters and an Invariant SPRT ................ 184
3.6.1 Testing the Variance of a Normal Population with
Unknown Mean ...................................... 185
3.6.2 Testing a Normal Population with Unknown Mean
and Variance (t-SPRT) ............................. 186
3.6.3 Rank-Order Nonparametric ISPRT for Lehmann's
Alternatives ...................................... 188
3.6.4 Linear Model with Nuisance Parameters ............. 188
4 Sequential Hypothesis Testing: Multiple Simple
Hypotheses ............................................... 191
4.1 The Matrix Sequential Probability Ratio Test ............. 191
4.2 The Structure of the Optimal Multihypothesis Sequential
Test in the iid Case ..................................... 193
4.3 Asymptotic Optimality of the MSPRT in the iid Case ....... 195
4.3.1 First-Order Asymptotic Optimality of the MSPRT
in the iid Case ................................... 195
4.3.2 Near Optimality of the MSPRT in the iid Case ...... 198
4.3.3 Higher-Order Asymptotic Approximations for the
Expected Sample Sizes ............................. 201
4.4 Asymptotic Optimality of the MSPRT in the General Non-
iid Case ................................................. 211
4.5 Invariant Multihypothesis Sequential Probability Ratio
Test ..................................................... 214
4.6 Multisample Slippage Problems ............................ 215
5 Sequential Hypothesis Testing: Composite Hypotheses ...... 223
5.1 Introduction ............................................. 223
5.2 Critique of the SPRT ..................................... 226
5.3 The Kiefer-Weiss Problem ................................. 227
5.3.1 Asymptotically Optimal Tests at an Intermediate
Point in the General Non-iid Case ................. 228
5.3.2 Asymptotically Optimal Tests at an Intermediate
Point in the iid Case ............................. 239
5.4 Uniformly First-Order Asymptotically Optimal Sequential
Tests .................................................... 244
5.4.1 The Generalized Sequential Likelihood Ratio Test .. 244
5.4.2 Adaptive Likelihood Ratio Tests with One-Stage
Delayed Estimators ................................ 256
5.4.3 Mixture-Based Sequential Likelihood Ratio Tests ... 269
5.4.4 Generalization to the Non-iid Case ................ 271
5.5 Nearly Minimax Sequential Tests of Composite Hypotheses
with Information Cost .................................... 280
5.5.1 Nearly Minimax Open Ended Sequential Tests ........ 281
5.5.2 Nearly Minimax Double-Sided Sequential Tests ...... 293
II. Changepoint Detection ..................................... 299
6 Statistical Models with Changes: Problem Formulations
and Optimality Criteria .................................. 301
6.1 Introduction ............................................. 301
6.2 Changepoint Models ....................................... 302
6.2.1 Models for Observations ........................... 303
6.2.2 Models for the Changepoint ........................ 304
6.2.3 Different Types of Changes ........................ 305
6.3 Optimality Criteria ...................................... 306
6.3.1 Bayesian Formulation .............................. 308
6.3.2 Generalized Bayesian Formulation .................. 310
6.3.3 Minimax Formulation ............................... 311
6.3.4 Multicyclic Detection of a Disorder in
a Stationary Regime ............................... 312
6.3.5 Uniform Optimality Criterion ...................... 313
6.3.6 Sequential Change Detection and Isolation ......... 314
7 Sequential Changepoint Detection: Bayesian Approach ...... 317
7.1 Optimality and Operating Characteristics of the
Shiryaev Procedure in the iid Case ....................... 317
7.1.1 The Shiryaev Procedure and Its Optimality ......... 317
7.1.2 Operating Characteristics ......................... 319
7.2 Asymptotic Optimality of the Shiryaev Procedure in the
Non-iid Case ............................................. 333
7.3 Asymptotically Optimal Detection Procedures under
Global False Alarm Probability Constraint ................ 341
7.3.1 The Detection Method .............................. 342
7.3.2 Asymptotic Optimality and Asymptotic Performance .. 342
7.4 Examples ................................................. 348
7.4.1 Detection of a Change in the Mean of a Gaussian
Autoregressive Process ............................ 348
7.4.2 Detection of Additive Changes in Linear State-
Space Models ...................................... 349
7.4.3 Detection of Nonadditive Changes in Mixture-Type
Models and Hidden Markov Models ................... 350
7.4.4 Continuous-Time Changepoint Detection in
Additive Itô Processes ............................ 351
7.4.5 Changepoint Detection in the Intensity of
a Nonhomogeneous Poisson Process .................. 353
7.5 Asymptotically Optimal Changepoint Detection Procedures
for Composite Hypotheses ................................. 354
7.6 A Generalized Bayesian Approach and the Shiryaev-
Roberts Procedure ........................................ 357
7.7 Comparison of the Shiryaev Procedure with Other
Procedures in the Bayesian Context ....................... 360
7.7.1 Asymptotic Analysis ............................... 360
7.7.2 Change Detection in an Exponential Distribution ... 362
8 Sequential Change Detection: Non-Bayesian Approaches ..... 365
8.1 Elementary Algorithms .................................... 365
8.1.1 Fixed Sample Size Algorithms - Shewhart Control
Charts ............................................ 366
8.1.2 Exponentially Weighted Moving Average Control
Charts ............................................ 373
8.1.3 Finite Moving Average Charts ...................... 375
8.2 The CUSUM Algorithm ...................................... 376
8.2.1 Intuitive Derivation .............................. 376
8.2.2 The CUSUM Algorithm as a Repeated SPRT ............ 377
8.2.3 The CUSUM Algorithm as a GLR Test ................. 379
8.2.4 The CUSUM Algorithm in the General Non-iid Case ... 380
8.2.5 Optimal Properties of the CUSUM Algorithm ......... 380
8.2.6 Operating Characteristics of the CUSUM Algorithm .. 386
8.2.7 A Generalization to a Special Non-iid Case ........ 405
8.2.8 CUSUM Optimality in the General Non-iid Case ...... 408
8.2.9 Local CUSUM ....................................... 415
8.3 Weighted CUSUM and GLR Algorithms for a Composite Post-
Change Hypothesis ........................................ 418
8.3.1 Asymptotic Optimality of WCUSUM and GLR
Algorithms in the iid Case ........................ 418
8.3.2 Asymptotic Optimality of WCUSUM and GCUSUM
Algorithms in the Non-iid Case .................... 433
8.4 The Shiryaev-Roberts Procedure and Its Modifications ..... 439
8.4.1 Optimality of the SR Procedure for a Change
Appearing after Many Reruns ....................... 439
8.4.2 The Shiryaev-Roberts-Pollak Procedure ............. 441
8.4.3 The Shiryaev-Roberts-r Procedure .................. 443
8.5 Weighted Shiryaev-Roberts Procedure ...................... 457
8.5.1 Asymptotic Properties of the Weighted SR
Procedure in the iid Case ......................... 458
8.5.2 Asymptotic Properties of the SR and Weighted SR
Procedures in the Non-iid Case .................... 464
9 Multichart Changepoint Detection Procedures for
Composite Hypotheses and Multipopulation Models .......... 465
9.1 Motivation for Applying Multichart Detection Procedures .. 465
9.2 Multichart CUSUM and Shiryaev-Roberts Procedures ......... 466
9.3 Quickest Detection of Unstructured Changes in Multiple
Populations .............................................. 473
9.4 Composite Hypothesis: Linear Gaussian Model,
Ј-Optimality ............................................. 478
9.4.1 The Concept of ε-Optimality ....................... 478
9.4.2 Detection of Changes in the Mean of a Gaussian
Vector ............................................ 480
9.4.3 Detection of Changes in the Linear Regression
Model ............................................. 487
10 Sequential Change Detection and Isolation ................ 493
10.1 Problem Formulation ...................................... 493
10.2 Fixed Sample Size Change Detection-Isolation Algorithms .. 494
10.2.1 A Multisample Sequential Slippage Problem ......... 494
10.2.2 A General Changepoint Model: Constrained Minimax
FSS Algorithm ..................................... 500
10.3 The Generalized CUSUM Change Detection-Isolation
Algorithms ............................................... 501
III. Applications ............................................. 511
11 Selected Applications .................................... 513
11.1 Navigation System Integrity Monitoring ................... 513
11.1.1 Introduction ...................................... 513
11.1.2 Inertial Navigation Integrity Monitoring: A Toy
Example ........................................... 515
11.1.3 Strapdown Inertial Reference Unit Integrity
Monitoring ........................................ 519
11.1.4 Radio-Navigation Integrity Monitoring ............. 523
11.2 Vibration-Based Structural Health Monitoring ............. 526
11.2.1 Introduction ...................................... 526
11.2.2 Subspace-Based Identification and Parameter
Estimating Function ............................... 527
11.2.3 Batch-Wise Change Detection Algorithm ............. 530
11.2.4 Sample-Wise Recursive CUSUM Detection Algorithm ... 532
11.2.5 Typical Application Examples ...................... 533
11.3 Rapid Detection of Intrusions in Computer Networks ....... 534
11.3.1 Introduction ...................................... 534
11.3.2 Anomaly-Based Intrusion Detection System .......... 535
11.3.3 Hybrid Anomaly-Signature Intrusion Detection
System ............................................ 543
Bibliography ............................................. 547
Index ......................................................... 575
|
