本书目录如下：

Preface v
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Recurrence Relations 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . 1
1.3 Number of Partitions of a Set . . . . . . . . . . . . . . . . 2
1.4Horner’s Method . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Sample Means and Variances . . . . . . . . . . . . . . . . . 3
1.6 Expected Family Size . . . . . . . . . . . . . . . . . . . . . 4
1.7 Poisson-Binomial Distribution . . . . . . . . . . . . . . . . 4
1.8 A Multinomial Test Statistic . . . . . . . . . . . . . . . . . 5
1.9 An Unstable Recurrence . . . . . . . . . . . . . . . . . . . . 6
1.10 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Power Series Expansions 12
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Expansion of P(s)n . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Application to Moments . . . . . . . . . . . . . . . 13
2.3 Expansion of eP(s) . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Moments to Cumulants and Vice Versa . . . . . . . 14
2.3.2 Compound Poisson Distributions . . . . . . . . . . 14
2.3.3 Evaluation of Hermite Polynomials . . . . . . . . . 15
x Contents
2.4Standard Normal Distribution Function . . . . . . . . . . . 15
2.5 Incomplete Gamma Function . . . . . . . . . . . . . . . . . 16
2.6 Incomplete Beta Function . . . . . . . . . . . . . . . . . . . 17
2.7 Connections to Other Distributions . . . . . . . . . . . . . 18
2.7.1 Chi-Square and Standard Normal . . . . . . . . . . 18
2.7.2 Poisson . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.7.3 Binomial and Negative Binomial . . . . . . . . . . 18
2.7.4 F and Student’s t . . . . . . . . . . . . . . . . . . . 19
2.7.5 Monotonic Transformations . . . . . . . . . . . . . 20
2.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Continued Fraction Expansions 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Wallis’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Equivalence Transformations . . . . . . . . . . . . . . . . . 27
3.4Gauss’s Expansion of Hypergeometric Functions . . . . . . 29
3.5 Expansion of the Incomplete Gamma Function . . . . . . 31
3.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Asymptotic Expansions 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Order Relations . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Finite Taylor Expansions . . . . . . . . . . . . . . . . . . . 39
4.4 Expansions via Integration by Parts . . . . . . . . . . . . . 4 2
4.4.1 Exponential Integral . . . . . . . . . . . . . . . . . . 4 2
4.4.2 Incomplete Gamma Function . . . . . . . . . . . . 4 3
4.4.3 Laplace Transforms . . . . . . . . . . . . . . . . . . 4 4
4.5 General Definition of an Asymptotic Expansion . . . . . . 4 4
4.6 Laplace’s Method . . . . . . . . . . . . . . . . . . . . . . . 4 4
4.6.1 Moments of an Order Statistic . . . . . . . . . . . . 4 5
4.6.2 Stirling’s Formula . . . . . . . . . . . . . . . . . . . 4 7
4.6.3 Posterior Expectations . . . . . . . . . . . . . . . . 4 7
4.7 Validation of Laplace’s Method . . . . . . . . . . . . . . . 4 8
4.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 9
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5 Solution of Nonlinear Equations 53
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2 Bisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.2.1 Computation of Quantiles by Bisection . . . . . . . 54
5.2.2 Shortest Confidence Interval . . . . . . . . . . . . . 55
5.3 Functional Iteration . . . . . . . . . . . . . . . . . . . . . . 57
5.3.1 Fractional Linear Transformations . . . . . . . . . . 58
Contents xi
5.3.2 Extinction Probabilities by Functional Iteration . . 59
5.4Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . 61
5.4.1 Division Without Dividing . . . . . . . . . . . . . . 63
5.4.2 Extinction Probabilities by Newton’s Method . . . 63
5.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6 Vector and Matrix Norms 68
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.2 Elementary Properties of Vector Norms . . . . . . . . . . . 68
6.3 Elementary Properties of Matrix Norms . . . . . . . . . . 70
6.4Iterativ e Solution of Linear Equations . . . . . . . . . . . . 73
6.4.1 Jacobi’s Method . . . . . . . . . . . . . . . . . . . . 74
6.4.2 Pan and Reif’s Iteration Scheme . . . . . . . . . . . 74
6.4.3 Equilibrium Distribution of a Markov Chain . . . . 74
6.5 Condition Number of a Matrix . . . . . . . . . . . . . . . . 75
6.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
7Linear Regression and Matrix Inversion 79
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.2 Motivation from Linear Regression . . . . . . . . . . . . . 80
7.3 Motivation from Multivariate Analysis . . . . . . . . . . . 80
7.4Definition of the Sweep Operator . . . . . . . . . . . . . . 81
7.5 Properties of the Sweep Operator . . . . . . . . . . . . . . 82
7.6 Applications of Sweeping . . . . . . . . . . . . . . . . . . . 84
7.7 Gram–Schmidt Orthogonalization . . . . . . . . . . . . . . 85
7.8 Woodbury’s Formula . . . . . . . . . . . . . . . . . . . . . . 86
7.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8 Eigenvalues and Eigenvectors 92
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 92
8.2 Jacobi’s Method . . . . . . . . . . . . . . . . . . . . . . . . 93
8.3 The Rayleigh Quotient . . . . . . . . . . . . . . . . . . . . 98
8.4Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
9 Splines 103
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 103
9.2 Definition and Basic Properties . . . . . . . . . . . . . . . 104
9.3 Applications to Differentiation and Integration . . . . . . 108
9.4Application to Nonparametric Regression . . . . . . . . . . 109
9.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
xii Contents
10 The EM Algorithm 115
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 115
10.2 General Definition of the EM Algorithm . . . . . . . . . . 116
10.3 Ascent Property of the EM Algorithm . . . . . . . . . . . 117
10.3.1 Technical Note . . . . . . . . . . . . . . . . . . . . . 119
10.4Allele Frequency Estimation . . . . . . . . . . . . . . . . . 119
10.5 Transmission Tomography . . . . . . . . . . . . . . . . . . 122
10.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
11 Newton’s Method and Scoring 130
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 130
11.2 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . 130
11.3 Scoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
11.4Generalized Linear Models . . . . . . . . . . . . . . . . . . 134
11.5 The Gauss–Newton Algorithm . . . . . . . . . . . . . . . . 135
11.6 Quasi-Newton Methods . . . . . . . . . . . . . . . . . . . . 136
11.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2
12 Variations on the EM Theme 143
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3
12.2 Iterative Proportional Fitting . . . . . . . . . . . . . . . . 14 3
12.3 EM Gradient Algorithm . . . . . . . . . . . . . . . . . . . . 14 5
12.3.1 Application to the Dirichlet Distribution . . . . . . 14 6
12.4Ba yesian EM . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7
12.5 Accelerated EM . . . . . . . . . . . . . . . . . . . . . . . . 14 7
12.6 EM Algorithms Without Missing Data . . . . . . . . . . . 14 9
12.6.1 Quadratic Lower Bound Principle . . . . . . . . . . 14 9
12.6.2 Elliptically Symmetric Densities and Lp
Regression . . . . . . . . . . . . . . . . . . . . . . . 150
12.6.3 Transmission Tomography Revisited . . . . . . . . 151
12.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
13 Convergence of Optimization Algorithms 160
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 160
13.2 Calculus Preliminaries . . . . . . . . . . . . . . . . . . . . . 161
13.3 Local Convergence . . . . . . . . . . . . . . . . . . . . . . . 162
13.4Global Convergence . . . . . . . . . . . . . . . . . . . . . . 166
13.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
14 Constrained Optimization 177
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Contents xiii
14.2 Necessary and Sufficient Conditions for a Minimum . . . . 178
14.3 Quadratic Programming with Equality Constraints . . . . 184
14.4 An Adaptive Barrier Method . . . . . . . . . . . . . . . . . 185
14.5 Standard Errors . . . . . . . . . . . . . . . . . . . . . . . . 187
14.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
15 Concrete Hilbert Spaces 191
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 191
15.2 Definitions and Basic Properties . . . . . . . . . . . . . . . 191
15.3 Fourier Series . . . . . . . . . . . . . . . . . . . . . . . . . . 194
15.4Orthogonal Polynomials . . . . . . . . . . . . . . . . . . . . 197
15.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
16 Quadrature Methods 207
16.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 207
16.2 Euler–Maclaurin Sum Formula . . . . . . . . . . . . . . . . 208
16.3 Romberg’s Algorithm . . . . . . . . . . . . . . . . . . . . . 210
16.4Adaptiv e Quadrature . . . . . . . . . . . . . . . . . . . . . 213
16.5 Taming Bad Integrands . . . . . . . . . . . . . . . . . . . . 213
16.6 Gaussian Quadrature . . . . . . . . . . . . . . . . . . . . . 214
16.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
17The Fourier Transform 221
17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 221
17.2 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . 222
17.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
17.4F urther Theory . . . . . . . . . . . . . . . . . . . . . . . . . 225
17.5 Edgeworth Expansions . . . . . . . . . . . . . . . . . . . . 229
17.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
18 The Finite Fourier Transform 235
18.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 235
18.2 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . 236
18.3 Derivation of the Fast Fourier Transform . . . . . . . . . . 237
18.4Appro ximation of Fourier Series Coefficients . . . . . . . . 238
18.5 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2
18.6 Time Series . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5
18.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 7
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
xiv Contents
19 Wavelets 252
19.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 252
19.2 Haar’s Wavelets . . . . . . . . . . . . . . . . . . . . . . . . 253
19.3 Histogram Estimators . . . . . . . . . . . . . . . . . . . . . 255
19.4Daub echies’ Wavelets . . . . . . . . . . . . . . . . . . . . . 256
19.5 Multiresolution Analysis . . . . . . . . . . . . . . . . . . . 262
19.6 Image Compression and the Fast Wavelet Transform . . . 263
19.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
20 Generating Random Deviates 269
20.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 269
20.2 The Inverse Method . . . . . . . . . . . . . . . . . . . . . . 270
20.3 Normal Random Deviates . . . . . . . . . . . . . . . . . . . 271
20.4Acceptance–Rejection Method . . . . . . . . . . . . . . . . 272
20.5 Ratio Method . . . . . . . . . . . . . . . . . . . . . . . . . . 277
20.6 Deviates by Definition . . . . . . . . . . . . . . . . . . . . . 278
20.7 Multivariate Deviates . . . . . . . . . . . . . . . . . . . . . 279
20.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
21 Independent Monte Carlo 286
21.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 286
21.2 Importance Sampling . . . . . . . . . . . . . . . . . . . . . 287
21.3 Stratified Sampling . . . . . . . . . . . . . . . . . . . . . . . 289
21.4An tithetic Variates . . . . . . . . . . . . . . . . . . . . . . . 290
21.5 Control Variates . . . . . . . . . . . . . . . . . . . . . . . . 291
21.6 Rao–Blackwellization . . . . . . . . . . . . . . . . . . . . . 292
21.7 Exact Tests of Independence in Contingency Tables . . . . 293
21.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
22 Bootstrap Calculations 299
22.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 299
22.2 Range of Applications . . . . . . . . . . . . . . . . . . . . . 300
22.3 Balanced Bootstrap Simulations . . . . . . . . . . . . . . . 305
22.4An tithetic Bootstrap Simulations . . . . . . . . . . . . . . 306
22.5 Importance Resampling . . . . . . . . . . . . . . . . . . . . 307
22.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312
23 Finite-State Markov Chains 314
23.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 314
23.2 Discrete-Time Markov Chains . . . . . . . . . . . . . . . . 315
23.3 Hidden Markov Chains . . . . . . . . . . . . . . . . . . . . 318
Contents xv
23.4Con tinuous-Time Markov Chains . . . . . . . . . . . . . . 321
23.5 Calculation of Matrix Exponentials . . . . . . . . . . . . . 324
23.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328
24 Markov Chain Monte Carlo 330
24.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 330
24.2 The Hastings–Metropolis Algorithm . . . . . . . . . . . . . 331
24.3 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . 332
24.4 Other Examples of Hastings–Metropolis Sampling . . . . . 334
24.5 Some Practical Advice . . . . . . . . . . . . . . . . . . . . . 336
24.6 Convergence of the Independence Sampler . . . . . . . . . 337
24.7 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . 339
24.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 0
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2
Index 345