随机过程讲义
Stochastic Processes
J. Chang
英文版
February 2, 2007
Contents
1 Markov chains 5
1.1 Specifying and simulating a Markov chain . . . . . . . . . . . . . . . . . . . 5
1.2 The Markov property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 “It’s all just matrix theory” . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 The basic limit theorem of Markov chains . . . . . . . . . . . . . . . . . . . 10
1.5 Stationary distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Irreducibility, periodicity, and recurrence . . . . . . . . . . . . . . . . . . . . 15
1.7 An aside on coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.8 Proof of the Basic Limit Theorem . . . . . . . . . . . . . . . . . . . . . . . 27
1.9 A SLLN for Markov chains . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2 Markov Chains: Examples and Applications 43
2.1 Branching Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2 Time Reversibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3 More on Time Reversibility: A Tandem Queue Model . . . . . . . . . . . . 49
2.4 The Metropolis method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.5 Simulated annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.5.1 Description of the method . . . . . . . . . . . . . . . . . . . . . . . . 58
2.5.2 The Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.6 Ergodicity Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.6.1 The Ergodic Coefficient . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.6.2 Sufficient Conditions for Weak and Strong Ergodicity . . . . . . . . 69
2.7 Proof of Main Theorem of Simulated Annealing . . . . . . . . . . . . . . . . 71
2.8 Card Shuffling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.8.1 “Top-in-at-random” Shuffle . . . . . . . . . . . . . . . . . . . . . . . 74
2.8.2 Threshold Phenomenon . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.8.3 A random time to exact stationarity . . . . . . . . . . . . . . . . . . 76
2.8.4 Strong Stationary Times . . . . . . . . . . . . . . . . . . . . . . . . . 77
2.8.5 Proof of threshold phenomenon in shuffling . . . . . . . . . . . . . . 78
2.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3 MRFs and HMMs 87
3.1 MRF’s on Graphs and HMM’s . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2 Bayesian Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3 Hammersley-Clifford Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.4 Long range dependence in the Ising model . . . . . . . . . . . . . . . . . . . 97
3.5 Hidden Markov chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.5.1 Description of the model . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.5.2 How to calculate likelihoods . . . . . . . . . . . . . . . . . . . . . . . 102
3.5.3 Maximum Likelihood and the EM algorithm . . . . . . . . . . . . . 104
3.5.4 Applying the EM algorithm to a hidden Markov chain . . . . . . . . 106
3.6 The Gibbs Sampler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4 Martingales 117
4.1 Why “martingale”? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.4 Optional sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.5 Stochastic integrals and option pricing . . . . . . . . . . . . . . . . . . . . . 126
4.6 Martingale convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.7 Stochastic approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
5 Brownian motion 149
5.1 The definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
5.2 Visualizing Brownian motion . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.3 The reflection principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
5.4 Conditional distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5.5 Existence and Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
5.6 The Brownian bridge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
5.6.1 A boundary crossing probability . . . . . . . . . . . . . . . . . . . . 164
5.6.2 Application to testing for uniformity . . . . . . . . . . . . . . . . . . 165
5.7 Boundary Crossing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.7.1 Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 168
5.7.2 Martingales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.8 Some confusing questions (or answers) . . . . . . . . . . . . . . . . . . . . . 172
5.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
6 Diffusions and Stochastic Calculus 179
6.1 Specifying a diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
6.2 A calculation with diffusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
6.3 Infinitesimal parameters of a function of a diffusion . . . . . . . . . . . . . . 186
6.4 Backward and forward equations . . . . . . . . . . . . . . . . . . . . . . . . 187
6.5 Stationary distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
6.6 Probability flux for diffusions . . . . . . . . . . . . . . . . . . . . . . . . . . 192
6.7 Quadratic Variation of Brownian Motion . . . . . . . . . . . . . . . . . . . . 194
6.8 Stochastic Differential Equations . . . . . . . . . . . . . . . . . . . . . . . . 196
6.9 Simple examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
6.10 The Black-Scholes Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
6.11 Stochastic Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7 Likelihood Ratios 209
7.1 The idea of likelihood ratios . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.2 The idea of importance sampling . . . . . . . . . . . . . . . . . . . . . . . . 210
7.3 A gambler’s ruin problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.4 Importance sampling for the gambler’s ruin . . . . . . . . . . . . . . . . . . 216
7.5 Brownian motion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
7.6 The Sequential Probability Ratio Test . . . . . . . . . . . . . . . . . . . . . 221
8 Extremes and Poisson clumping 223
8.1 The Poisson clumping heuristic . . . . . . . . . . . . . . . . . . . . . . . . . 223
A Convergence theorems 227
B Conditioning 229
B.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
B.2 Summary of some rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
B.3 Conditional probabilities and expectations . . . . . . . . . . . . . . . . . . . 232