Contents
1 Introduction 10
I Introduction to Stochastic Dynamics 17
2 Introduction to Programming 18
2.1 Programming Techniques . . . . . . . . . . . . . . . . . . . . . 18
2.1.1 Writing Pseudocode . . . . . . . . . . . . . . . . . . . 18
2.1.2 First Steps in R . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 Functions and Conditions . . . . . . . . . . . . . . . . 28
2.2 More R Programming . . . . . . . . . . . . . . . . . . . . . . 33
2.2.1 Loops and Repetition . . . . . . . . . . . . . . . . . . . 33
2.2.2 Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2.3 More Features . . . . . . . . . . . . . . . . . . . . . . . 39
3 Mathematical Preliminaries 41
3.1 The Nuts and Bolts . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.1 Sets and Logic . . . . . . . . . . . . . . . . . . . . . . 41
3.1.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.1.3 Infinities . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 The Real Numbers . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.1 Real Sequences . . . . . . . . . . . . . . . . . . . . . . 49
1
Stochastic Economic Dynamics John Stachurski
3.2.2 Suprema and Infima . . . . . . . . . . . . . . . . . . . 53
3.2.3 Functions of a Real Variable . . . . . . . . . . . . . . . 56
4 Analysis in Metric Space 59
4.1 A First Look at Metric Space . . . . . . . . . . . . . . . . . . 59
4.1.1 Distances and Norms . . . . . . . . . . . . . . . . . . . 61
4.1.2 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.3 Open Sets, Closed Sets . . . . . . . . . . . . . . . . . . 66
4.2 Further Properties . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2.1 Complete Sets, Compact Sets . . . . . . . . . . . . . . 70
4.2.2 Convergence of Functions . . . . . . . . . . . . . . . . 74
4.2.3 Optimization and Fixed Points . . . . . . . . . . . . . 75
5 Introduction to Dynamics 82
5.1 Deterministic Dynamical Systems . . . . . . . . . . . . . . . . 82
5.1.1 The Basic Model . . . . . . . . . . . . . . . . . . . . . 82
5.1.2 Chaotic Dynamic Systems . . . . . . . . . . . . . . . . 90
5.1.3 Equivalent Dynamics and Linearization . . . . . . . . . 93
5.2 Introduction to Dynamic Optimization . . . . . . . . . . . . . 95
5.2.1 The Sequential Approach . . . . . . . . . . . . . . . . . 96
5.2.2 Introduction to Dynamic Programming . . . . . . . . . 99
5.2.3 Dynamics of the Optimal Path . . . . . . . . . . . . . 100
6 Introduction to Finite Markov Chains 103
6.1 Finite State Markov Chains . . . . . . . . . . . . . . . . . . . 103
6.1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.1.2 Marginal Distributions . . . . . . . . . . . . . . . . . . 110
6.1.3 Other Identities . . . . . . . . . . . . . . . . . . . . . . 113
6.2 Joint Distributions . . . . . . . . . . . . . . . . . . . . . . . . 117
6.2.1 Constructing Joint Distributions . . . . . . . . . . . . . 117
6.2.2 Formalities . . . . . . . . . . . . . . . . . . . . . . . . 123
December 26, 2006 Page 2 of 359
Stochastic Economic Dynamics John Stachurski
7 Further Topics for Finite MCs 129
7.1 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.1.1 Stationary Distributions . . . . . . . . . . . . . . . . . 131
7.1.2 Convergence of Distributions . . . . . . . . . . . . . . . 135
7.1.3 The Law of Large Numbers . . . . . . . . . . . . . . . 139
7.2 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
7.2.1 Outline of the Problem . . . . . . . . . . . . . . . . . . 141
7.2.2 Value Iteration . . . . . . . . . . . . . . . . . . . . . . 145
7.2.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . 150
8 Stochastic Difference Equations 153
8.1 First Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
8.1.1 Basic Models and Simulation . . . . . . . . . . . . . . 153
8.1.2 Distribution Dynamics . . . . . . . . . . . . . . . . . . 162
8.1.3 Stationarity and Ergodicity . . . . . . . . . . . . . . . 168
8.2 Application: Stochastic Speculative Price . . . . . . . . . . . . 171
8.2.1 The Model . . . . . . . . . . . . . . . . . . . . . . . . . 172
8.2.2 Solving the Model . . . . . . . . . . . . . . . . . . . . . 179
8.2.3 Dynamics of the Model . . . . . . . . . . . . . . . . . . 183
II Advanced Techniques 187
9 Measure and Integral 188
9.1 A Crash Course in Measure Theory . . . . . . . . . . . . . . . 188
9.1.1 Lebesgue Measure . . . . . . . . . . . . . . . . . . . . . 188
9.1.2 Lebesgue Measure in Rn . . . . . . . . . . . . . . . . . 193
9.1.3 More General Measures, Probabilities . . . . . . . . . . 194
9.2 Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
December 26, 2006 Page 3 of 359
Stochastic Economic Dynamics John Stachurski
9.2.1 The Lebesgue Integral on R . . . . . . . . . . . . . . . 199
9.2.2 The General Integral . . . . . . . . . . . . . . . . . . . 204
9.2.3 Finishing Touches . . . . . . . . . . . . . . . . . . . . . 210
9.3 Probability and Random Variables . . . . . . . . . . . . . . . 215
9.3.1 Random Variables . . . . . . . . . . . . . . . . . . . . 215
9.3.2 Distributions of Random Variables . . . . . . . . . . . 218
9.3.3 Densities . . . . . . . . . . . . . . . . . . . . . . . . . . 222
10 General State Markov Chains 226
10.1 Basic Constructions . . . . . . . . . . . . . . . . . . . . . . . . 226
10.1.1 Stochastic Kernels . . . . . . . . . . . . . . . . . . . . 226
10.1.2 Markov Kernels and SDEs . . . . . . . . . . . . . . . . 231
10.1.3 The Fundamental Recursion, Again . . . . . . . . . . . 234
10.2 Expectations, Operators and Distributions . . . . . . . . . . . 237
10.2.1 More Operators . . . . . . . . . . . . . . . . . . . . . . 237
10.2.2 Monotone Markov Chains. . . . . . . . . . . . . . . . . 240
10.2.3 Density Kernels . . . . . . . . . . . . . . . . . . . . . . 241
11 Further Theory of General State MCs 246
11.1 Notions of Convergence . . . . . . . . . . . . . . . . . . . . . . 246
11.1.1 Convergence of Random Variables . . . . . . . . . . . . 246
11.1.2 Weak Convergence . . . . . . . . . . . . . . . . . . . . 250
11.1.3 Convergence in Total Variation . . . . . . . . . . . . . 253
11.2 Markov Chains as Stochastic Processes . . . . . . . . . . . . . 255
11.2.1 First Steps . . . . . . . . . . . . . . . . . . . . . . . . . 256
11.2.2 Joint Distributions of Stochastic Processes . . . . . . . 257
11.2.3 Back to Markov Chains . . . . . . . . . . . . . . . . . 260
December 26, 2006 Page 4 of 359
Stochastic Economic Dynamics John Stachurski
12 Dynamics of General State MCs 262
12.1 Existence of Stationary Distributions . . . . . . . . . . . . . . 263
12.1.1 Existence for Feller Chains . . . . . . . . . . . . . . . . 264
12.1.2 Noncompact State Space . . . . . . . . . . . . . . . . . 268
12.1.3 Stationary Densities . . . . . . . . . . . . . . . . . . . 273
12.2 Stability in the General State Case . . . . . . . . . . . . . . . 281
12.2.1 Stability in the Density Case . . . . . . . . . . . . . . . 281
12.2.2 Classical Theory of MCs . . . . . . . . . . . . . . . . . 285
12.2.3 Sample Path Properties . . . . . . . . . . . . . . . . . 285
13 Stochastic Dynamic Programming 286
13.1 Basic Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
13.1.1 Statement of the Problem . . . . . . . . . . . . . . . . 287
13.1.2 Control Policies . . . . . . . . . . . . . . . . . . . . . . 289
13.1.3 Optimality . . . . . . . . . . . . . . . . . . . . . . . . . 294
13.2 Application: Optimal Growth . . . . . . . . . . . . . . . . . . 301
13.2.1 Optimality . . . . . . . . . . . . . . . . . . . . . . . . . 301
13.2.2 The Euler Equation . . . . . . . . . . . . . . . . . . . . 304
13.2.3 Dynamic Properties . . . . . . . . . . . . . . . . . . . . 310
14 More Stochastic Dynamic Programming 316
14.1 Extensions to the Theory . . . . . . . . . . . . . . . . . . . . . 316
14.1.1 Monotone Policy Rules . . . . . . . . . . . . . . . . . . 316
14.1.2 Unbounded Rewards, Part I . . . . . . . . . . . . . . . 321
14.1.3 Unbounded Rewards, Part II . . . . . . . . . . . . . . . 323
14.2 Further Applications . . . . . . . . . . . . . . . . . . . . . . . 331
14.2.1 The Commodity Pricing Model . . . . . . . . . . . . . 331
14.2.2 Optimal Growth with Correlated Shocks . . . . . . . . 331
14.2.3 Asset Prices and Production . . . . . . . . . . . . . . . 331
December 26, 2006 Page 5 of 359
Stochastic Economic Dynamics John Stachurski
15 Numerical Methods for Dynamic Programming 332
15.1 Algorithms and Methods . . . . . . . . . . . . . . . . . . . . . 332
15.1.1 Value Iteration . . . . . . . . . . . . . . . . . . . . . . 332
15.1.2 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . 335
15.1.3 Policy Function Iteration . . . . . . . . . . . . . . . . . 338
15.2 Finite State/Action Models . . . . . . . . . . . . . . . . . . . 338
15.2.1 Set Up . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
15.2.2 Value Iteration . . . . . . . . . . . . . . . . . . . . . . 340
15.2.3 Policy Iteration . . . . . . . . . . . . . . . . . . . . . . 343
15.3 Continuous State/Action Models . . . . . . . . . . . . . . . . 346
15.3.1 Nonexpansive Function Approximators . . . . . . . . . 346
15.3.2 Fitted Value Iteration . . . . . . . . . . . . . . . . . . 346
15.3.3 Fitted Policy Function Iteration . . . . . . . . . . . . . 346
A Appendix 347
A.1 Appendix to Chapter 4 . . . . . . . . . . . . . . . . . . . . . . 347
A.2 Appendix to Chapter 6 . . . . . . . . . . . . . . . . . . . . . . 350
A.3 Appendix to Chapter 14 . . . . . . . . . . . . . . . . . . . . . 352