Sequential change detection and hypothesis testing: general non-i.i.d. stochastic models and asymptotically optimal rules

✍ Scribed by Tartakovsky, Alexander

• Publisher: CRC Press
• Year: 2020
• Tongue: English
• Leaves: 321
• Series: Monographs on statistics and applied probability (Series)
• Category: Library

✦ Synopsis

Sequential hypothesis testing in multiple data streams -- Sequential detection of changes : changepoint models, performance metrics and optimality criteria -- Bayesian quickest change detection in a single population -- Nearly optimal pointwise and minimax change detection in a single population -- Change detection rules optimal for the maximal detection probability criterion -- Quickest change detection in multiple streams -- Joint changepoint detection and identification -- Applications.;"Statistical methods for sequential hypothesis testing and changepoint detection have applications across many fields. This book presents an overview of methodology in these related areas, providing a synthesis of research from the last few decades"--

✦ Table of Contents

Cover......Page 1
Half Title......Page 2
Series Page......Page 3
Title Page......Page 4
Copyright Page......Page 5
Dedication......Page 6
Contents......Page 8
Preface......Page 12
Notation and Symbols......Page 14
Introduction......Page 18
1.1 Introduction......Page 22
1.2 Sequential Multistream Hypothesis Testing Problem......Page 23
1.3 Generalized Likelihood Ratio and Mixture Sequential Tests......Page 24
1.4.1.1 Upper Bounds on the Error Probabilities......Page 27
1.4.1.2 Error Exponents......Page 28
1.4.1.3 Monte Carlo Importance Sampling......Page 30
1.4.1.4 Asymptotic Optimality of GSLRT and MSLRT......Page 33
1.4.2 The Case of Independent Data Streams......Page 36
1.4.2.2 Scalability in the Case of Independent Streams......Page 37
1.4.3 Examples......Page 39
1.4.4 Monte Carlo Simulations......Page 42
1.5.1 Preliminaries......Page 47
1.5.2 Asymptotic Approximations for the Probabilities of Errors......Page 50
1.5.3.1 Asymptotic Approximations for the ESS Under Hypothesis HB and Under Hypothesis H0 in the Asymmetric Case......Page 52
1.5.3.2 Asymptotic Approximations for the ESS Under Hypothesis H0 in the General Case......Page 57
1.5.4.1 Uniform Asymptotic Optimality......Page 73
1.5.4.2 Bayesian-type Asymptotic Optimality......Page 74
1.5.4.3 Asymptotic Minimax Properties with Respect to Kullback–Leibler Information......Page 78
1.5.4.4 Further Optimization and MC Simulations......Page 79
2.1 Introduction......Page 84
2.2.1.1 A Single Stream Scenario......Page 85
2.2.1.2 A Multistream Scenario......Page 86
2.2.2.2 Models......Page 87
2.3.2 Measures of the False Alarm Risk......Page 90
2.3.2.1 Average Run Length to False Alarm......Page 91
2.3.2.3 Global Probability of False Alarm......Page 92
2.3.2.4 Local Probabilities of False Alarm......Page 93
2.3.3 An Expected Delay to Detection in a General Case......Page 95
2.3.4 Bayesian Criteria with Respect to the Expected Delay to Detection......Page 96
2.3.5 Minimax Criteria with Respect to the Expected Delay to Detection......Page 98
2.3.7 Criteria Maximizing Probability of Detection......Page 100
2.3.8 Asymptotic Optimality Criteria......Page 102
3.1 Introduction......Page 104
3.2 The Shiryaev and Shiryaev–Roberts Mixture Rules......Page 106
3.3 Asymptotic Problems......Page 107
3.4.1 Assumptions......Page 109
3.4.2 Heuristics......Page 110
3.4.3 Asymptotic Optimality......Page 112
3.5 Asymptotic Performance of the Mixture Shiryaev–Roberts Rule......Page 120
3.6 Asymptotic Optimality with Respect to the Integrated Risk......Page 125
3.7 The Case of a Simple Post-Change Hypothesis......Page 129
3.8 The Case of Independent Observations......Page 131
3.9 The i.i.d. Case......Page 135
3.10 Window-Limited Change Detection Rules......Page 137
3.11 Sufficient Conditions of Asymptotic Optimality for Markov Processes......Page 143
3.12 Asymptotic Optimality for Hidden Markov Models......Page 150
3.12.1 Markov Random Walk Representation of the LLR for HHM......Page 151
3.12.2 Asymptotic Optimality......Page 153
3.12.3 Higher Order Asymptotic Approximations for the Average Detection Delay and PFA......Page 156
3.12.4 The Case of Conditionally Independent Observations......Page 161
3.13 Additional Examples......Page 163
3.14 Concluding Remarks......Page 168
4.2.1 Problem Setup......Page 170
4.2.2.1 The Non-i.i.d. Case......Page 171
4.2.2.2 The Case of LLR with Independent Increments......Page 177
4.3 Examples......Page 178
4.4 Monte Carlo Simulations......Page 182
5.1 Introduction......Page 184
5.2.1 Optimality with Respect to the Expected Detection Delay......Page 185
5.2.2 Maximal Average Probability of Detection: the Bayesian Approach......Page 186
5.2.3 Maximin Frequentist Criteria......Page 193
5.3.1 Bayes Optimal Change Detection Rule......Page 197
5.3.2 Maximin Optimal Change Detection Rule......Page 200
5.4 Concluding Remarks......Page 201
6.1 Introduction......Page 202
6.2.1 The General Multistream Model......Page 203
6.2.2.1 The General Case......Page 204
6.2.2.2 Independent Streams......Page 206
6.3 Asymptotic Optimality Problems and Assumptions......Page 207
6.4 Asymptotic Lower Bounds for Moments of the Detection Delay and Average Risk Function......Page 209
6.5.1 Asymptotic Optimality of the Double-Mixture Rule TpA,W......Page 210
6.5.2 Asymptotic Optimality of the Double-Mixture Rule TpA,W......Page 214
6.6 Asymptotic Optimality with Respect to the Average Risk......Page 218
6.7 Asymptotic Optimality for a Putative Value of the Post-Change Parameter......Page 220
6.8 Asymptotic Optimality in the Case of Independent Streams......Page 221
6.9 Examples......Page 222
6.10 Discussion and Remarks......Page 226
7.1 Introduction......Page 228
7.2 The Model and the Detection–Identification Rule......Page 229
7.3 The Optimization Problem and Assumptions......Page 230
7.4 Upper Bounds on Probabilities of False Alarm and Misidentification......Page 232
7.5 Lower Bounds on the Moments of the Detection Delay......Page 234
7.6 Asymptotic Optimality of the Detection–Identification Rule δA......Page 238
7.7 An Example......Page 242
7.8 Concluding Remarks......Page 243
8.1 Application to Object Track Management in Sonar Systems......Page 248
8.2 Application to Detection of Traces of Space Objects......Page 251
8.3 Application to Detection of Unauthorized Break-ins in Computer Networks......Page 256
Appendix A: Useful Auxiliary Results......Page 260
B.1 Standard Modes of Convergence......Page 264
B.2 Complete and r-Quick Convergence......Page 266
C.1 The Doob–Wald Identities......Page 270
C.2 Inequalities for Martingales......Page 272
Appendix D: Markov Processes......Page 274
D.2 Stationary and Quasi-stationary Distributions......Page 275
D.3.1 Correlation Inequality......Page 278
D.4 Markov Random Walks......Page 279
D.4.1 Wald’s Identity for Markov Random Walks......Page 280
D.4.2 Rates of Convergence in the SLLN for Markov Random Walks......Page 281
D.5 Hidden Markov Models......Page 282
E.1.1 The Distribution of the Overshoot......Page 284
E.1.2 Approximations for the Expectation of the Stopping Time......Page 289
E.2 A General Multidimensional Renewal Theorem......Page 291
E.3 Expectation of First Exit Times for Markov Random Walks......Page 294
F.1 Nonlinear Renewal Theory for Perturbed Random Walks......Page 296
F.2 General Nonlinear Renewal Theory......Page 300
F.3 Markov Nonlinear Renewal Theory......Page 303
Bibliography......Page 306
Index......Page 318

✦ Subjects

Mathematical statistics;MATHEMATICS / Probability & Statistics / Bayesian Analysis;MATHEMATICS / Probability & Statistics / General;Sequential analysis;Electronic books