Normal Approximation by Stein’s Method                              springer
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 The Central Limit Theorem . . . . . . . . . . . . . . . . . . . . . 1
1.2 ABriefHistoryofStein’sMethod . . . . . . . . . . . . . . . . . . 3
1.3 TheBasic IdeaofStein’sMethod . . . . . . . . . . . . . . . . . . 4
1.4 Outline and Summary . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Fundamentals of Stein’s Method . . . . . . . . . . . . . . . . . . . . 13
2.1 Stein’sEquation . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Properties of the Solutions . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Construction of Stein Identities . . . . . . . . . . . . . . . . . . . 18
2.3.1 Sums of Independent Random Variables . . . . . . . . . . 19
2.3.2 Exchangeable Pairs . . . . . . . . . . . . . . . . . . . . . 21
2.3.3 ZeroBias . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.4 SizeBias . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 A General Framework for Stein Identities and Normal
Approximation for Lipschitz Functions . . . . . . . . . . . . . . . 36
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3 Berry–Esseen Bounds for Independent Random Variables . . . . . . 45
3.1 Normal Approximation with Lipschitz Functions . . . . . . . . . . 46
3.2 The Lindeberg Central Limit Theorem . . . . . . . . . . . . . . . 48
3.3 Berry–Esseen Inequality: The Bounded Case . . . . . . . . . . . . 49
3.4 The Berry–Esseen Inequality for Unbounded Variables . . . . . . . 53
3.4.1 The Concentration Inequality Approach . . . . . . . . . . 53
3.4.2 An Inductive Approach . . . . . . . . . . . . . . . . . . . 57
3.5 A Lower Berry–Esseen Bound . . . . . . . . . . . . . . . . . . . 59
4 L1 Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1 Sums of Independent Variables . . . . . . . . . . . . . . . . . . . 65
4.1.1 L1 Berry–Esseen Bounds . . . . . . . . . . . . . . . . . . 65
4.1.2 ContractionPrinciple . . . . . . . . . . . . . . . . . . . . 69
4.2 HierarchicalStructures . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2.1 Bounds to the Normal for Approximately Linear Recursions 78
4.2.2 Normal Bounds for Hierarchical Sequences . . . . . . . . . 82
4.2.3 Convergence Rates for the Diamond Lattice . . . . . . . . 87
4.3 ConeMeasureProjections . . . . . . . . . . . . . . . . . . . . . . 88
4.3.1 Coupling Constructions for Coordinate Symmetric
Variables andTheirProjections . . . . . . . . . . . . . . . 90
4.3.2 Construction and Bounds for Cone Measure . . . . . . . . 94
4.4 Combinatorial Central Limit Theorems . . . . . . . . . . . . . . . 100
4.4.1 Use of the Exchangeable Pair . . . . . . . . . . . . . . . . 102
4.4.2 Construction and Bounds for the Combinatorial Central
Limit Theorem . . . . . . . . . . . . . . . . . . . . . . . . 105
4.5 Simple Random Sampling . . . . . . . . . . . . . . . . . . . . . . 111
4.6 Chatterjee’s L1 Theorem . . . . . . . . . . . . . . . . . . . . . . 116
4.7 Locally Dependent Random Variables . . . . . . . . . . . . . . . . 133
4.8 Smooth Function Bounds . . . . . . . . . . . . . . . . . . . . . . 136
4.8.1 Fast Rates for Smooth Functions . . . . . . . . . . . . . . 136
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5 L∞ by Bounded Couplings . . . . . . . . . . . . . . . . . . . . . . . 147
5.1 Bounded Zero Bias Couplings . . . . . . . . . . . . . . . . . . . . 147
5.2 Exchangeable Pairs, Kolmogorov Distance . . . . . . . . . . . . . 149
5.3 Size Biasing, Kolmogorov Bounds . . . . . . . . . . . . . . . . . 156
5.4 Size Biasing and Smoothing Inequalities . . . . . . . . . . . . . . 161
6 L∞: Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
6.1 Combinatorial Central Limit Theorem . . . . . . . . . . . . . . . 167
6.1.1 UniformDistributionontheSymmetricGroup . . . . . . . 168
6.1.2 DistributionConstantonConjugacyClasses . . . . . . . . 183
6.1.3 Doubly Indexed Permutation Statistics . . . . . . . . . . . 201
6.2 Patterns in Graphs and Permutations . . . . . . . . . . . . . . . . 202
6.3 The Lightbulb Process . . . . . . . . . . . . . . . . . . . . . . . . 210
6.4 Anti-voter Model . . . . . . . . . . . . . . . . . . . . . . . . . . 213
6.5 Binary Expansion of a Random Integer . . . . . . . . . . . . . . . 217
7 Discretized Normal Approximation . . . . . . . . . . . . . . . . . . . 221
7.1 PoissonBinomial . . . . . . . . . . . . . . . . . . . . . . . . . . 222
7.2 Sum of Independent Integer Valued Random Variables . . . . . . . 227
8 Non-uniform Bounds for Independent Random Variables . . . . . . 233
8.1 A Non-uniform Concentration Inequality . . . . . . . . . . . . . . 233
8.2 Non-uniform Berry–Esseen Bounds . . . . . . . . . . . . . . . . . 237
9 Uniform and Non-uniform Bounds Under Local Dependence . . . . 245
9.1 Uniform and Non-uniform Berry–Esseen Bounds . . . . . . . . . 246
9.2 Outline of Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
9.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
10 Uniform and Non-uniform Bounds for Non-linear Statistics . . . . . 257
10.1 Introduction and Main Results . . . . . . . . . . . . . . . . . . . . 257
10.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
10.2.1 U-statistics . . . . . . . . . . . . . . . . . . . . . . . . . . 260
10.2.2 Multi-sample U-statistics . . . . . . . . . . . . . . . . . . 262
10.2.3 L-statistics . . . . . . . . . . . . . . . . . . . . . . . . . . 265
10.2.4 Random Sums of Independent Random Variables
with Non-random Centering . . . . . . . . . . . . . . . . . 270
10.2.5 Functions of Non-linear Statistics . . . . . . . . . . . . . . 273
10.3 Uniform and Non-uniform Randomized Concentration Inequalities 277
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
11 Moderate Deviations . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
11.1 A Cramér Type Moderate Deviation Theorem . . . . . . . . . . . 293
11.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
11.3 PreliminaryLemmas . . . . . . . . . . . . . . . . . . . . . . . . . 298
11.4 Proofs ofMainResults . . . . . . . . . . . . . . . . . . . . . . . 302
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
12 Multivariate Normal Approximation . . . . . . . . . . . . . . . . . . 313
12.1 Multivariate Normal Approximation via Size Bias Couplings . . . 314
12.2 Degrees of Random Graphs . . . . . . . . . . . . . . . . . . . . . 315
12.3 Multivariate Exchangeable Pairs . . . . . . . . . . . . . . . . . . . 325
12.4 Local Dependence, and Bounds in Kolmogorov Distance . . . . . 331
13 Non-normal Approximation . . . . . . . . . . . . . . . . . . . . . . . 343
13.1 Stein’s Method via the Density Approach . . . . . . . . . . . . . . 343
13.1.1 TheSteinCharacterizationandEquation . . . . . . . . . . 344
13.1.2 Properties of the Stein Solution . . . . . . . . . . . . . . . 346
13.2 L1 and L∞ Bounds via Exchangeable Pairs . . . . . . . . . . . . . 347
13.3 The Curie–Weiss Model . . . . . . . . . . . . . . . . . . . . . . . 353
13.4 Exponential Approximation . . . . . . . . . . . . . . . . . . . . . 358
13.4.1 Spectrum of the Bernoulli–Laplace Markov Chain . . . . . 358
13.4.2 FirstPassageTimes . . . . . . . . . . . . . . . . . . . . . 363
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
14 Group Characters and Malliavin Calculus . . . . . . . . . . . . . . . 371
14.1 NormalApproximationforGroupCharacters . . . . . . . . . . . . 371
14.1.1 O(2n,R) . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
14.1.2 SO(2n+1,R) . . . . . . . . . . . . . . . . . . . . . . . . 380
14.1.3 USp(2n,C) . . . . . . . . . . . . . . . . . . . . . . . . . 381
14.2 Stein’s Method and Malliavin Calculus . . . . . . . . . . . . . . . 381
Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391