A First Look at Stochastic Processes

by Jeffrey S. Rosenthal

This book describes the mathematical theory of stochastic processes, i.e. quantities that proceed randomly in time. It was published by World Scientific in 2019. It may be ordered for US\$38 directly from the publisher, or from e.g. amazon.com or amazon.ca or kindle or kobo. See the Preface and Contents below, the errata and supplement1 and supplement2, and the related computer simulations.

(See also my Rigorous Probability Theory book, and my free introductory-level probability and statistics book.)

Student comments from anonymous course evaluations:

"His textbook was perfection: it was organized and rigorous but also managed to distill complex concepts/proofs down to straightforward, intuitive ideas."

"The textbook was very well written, providing detailed explanations and solutions, and the appendix helped refreshing our memory when it came to using material from previous courses."

"The book written by the instructor is a very helpful source. Going through it rigorously (as there are lots of proofs) provides me with a deep understanding of stochastic processes."

See also this clever related pandemic cartoon drawn by a student.

PREFACE

This book describes the mathematical theory of stochastic processes, i.e. of quantities that proceed randomly as a function of time. A main example is Markov chains, which are the focus of the first half of the book and also make frequent appearances in the second half. Simple rules about how processes proceed at each step lead to many surprising, interesting, and elegant theorems about what happens in the long run.

I have tried to communicate the excitement and intrigue of this subject without requiring extensive background knowledge. The book develops a fairly complete mathematical theory of discrete Markov chains and martingales, and then in Section 4 gives some initial ideas about continuous processes. Along the way, it discusses a number of interesting applications, including gambler's ruin, random walks on graphs, sequence waiting times, stock option pricing, branching processes, Markov chain Monte Carlo (MCMC) algorithms, and more.

The book arose from point-form lecture notes. Although it was later expanded into complete sentences and paragraphs, it retains its original brevity, with short paragraphs and each "point" on its own line, to communicate ideas one at a time. Some excessively technical material is written in smaller font and may be ignored on first reading. There are also links to some animated simulations; for additional links and updates and information, visit: www.probability.ca/spbook

The target audience for this book is upper-year undergraduate and graduate-level students in Statistics, Mathematics, Computer Science, Economics, Finance, Engineering, Physics, and other subjects which involve logical reasoning and mathematical foundations, and which require working knowledge of how probabilities progress in time. The prerequisites to reading this book are a solid background in basic undergraduate-level mathematics, including advanced calculus and basic linear algebra and basic real analysis (not including measure theory), plus undergraduate-level probability theory including expected values, distributions, limit theorems, etc.

Appendix A contains many basic facts from elementary probability and mathematics, as needed. It is referred to frequently in the text, to clarify arguments and to fill in any knowledge gaps. Appendix B lists references for further reading about stochastic processes.

Various problems are sprinkled throughout the book, and should be attempted for greater understanding. More involved problems are marked with (*). Problems marked [sol] have full solutions in Appendix C.

To ease understanding and memory, I have provided colorful names for many of the results, like the Sum Lemma and Recurrence Equivalences Theorem and Closed Subset Note and Vanishing Probabilities Proposition. Hopefully the names are helpful -- otherwise just use their numbers instead. But be warned that if you use these names in conversation, then readers of other books might not know what you are talking about!

Acknowledgements: This text grew out of my lecturing the course STA 447/2006: Stochastic Processes at the University of Toronto over a period of many years. I thank my colleagues for giving me that opportunity. I also thank the many students who have studied these topics with me; their reactions and questions have been a major source of inspiration.

Jeffrey S. Rosenthal
Toronto, Canada, 2019
www.probability.ca/jeff
Contact me

TABLE OF CONTENTS:

```Preface                                                     v
About the Author                                          vii
1 Markov Chain Probabilities                                1
1.1  First Example: The Frog Walk . . . . .    . . .  .  1
1.2  Markov Chain Definitions . . . . . . .    . . .  .  2
1.3  Examples of Markov Chains . . . . . .     . . .  .  4
1.4  Multi-Step Transitions . . . . . . . .    . . .  .  8
1.5  Recurrence and Transience . . . . . .     . . .  . 11
1.6  Communicating States and Irreducibility . . . .  . 18
1.7  Application -- Gambler's Ruin . . . . .   . . . .  28
2 Markov Chain Convergence                                 35
2.1  Stationary Distributions . . . . . . . .    . .  . 35
2.2  Searching for Stationarity . . . . . . . .  . .  . 37
2.3  Obstacles to Convergence . . . . . . . .    . .  . 42
2.4  Convergence Theorem . . . . . . . . .       . .  . 45
2.5  Periodic Convergence . . . . . . . . .      . .  . 55
2.6  Application -- MCMC Algorithms (Discrete)   . .  . 59
2.7  Application -- Random Walks on Graphs . .   . .  . 62
2.8  Mean Recurrence Times . . . . . . . .       . .  . 68
2.9  Application -- Sequence Waiting Times. . .  . .  . 71
3 Martingales                                              75
3.1  Martingale Definitions . . . . . . . . . . .     . 75
3.2  Stopping Times and Optional Stopping . . . .     . 78
3.3  Wald's Theorem. . . . . . . . . . . . . .        . 84
3.4  Application -- Sequence Waiting Times (Revisited). 89
3.5  Martingale Convergence Theorem. . . . . . .      . 91
3.6  Application -- Branching Processes . . . . . .   . 94
3.7  Application -- Stock Options (Discrete) . . . .  . 97
4 Continuous Processes                                    103
4.1  Brownian Motion . . . . . . . . . . . .       . . 103
4.2  Application -- Stock Options (Continuous) . . . . 109
4.3  Poisson Processes . . . . . . . . . . . .     . . 113
4.4  Continuous-Time, Discrete-Space Processes . . . . 122
4.5  Application -- Queueing Theory . . . . . .    . . 132
4.6  Application -- Renewal Theory . . . . . . .   . . 139
4.7  Continuous-Space Markov Chains. . . . . .     . . 148
4.8  Application -- MCMC Algorithms (Continuous)   . . 154
A Appendix: Background                                    159
A.1 Notation. . . . . . . . . . . .       . .  . . . . 159
A.2 Basic Probability Theory . . . . .    . .  . . . . 160
A.3 Standard Probability Distributions .  . .  . . . . 161
A.4 Infinite Series and Limits . . . . .  . .  . . . . 163
A.5 Bounded, Finite, and Infinite . . .   . .  . . . . 165
A.6 Conditioning . . . . . . . . . .      . .  . . . . 166
A.7 Convergence of Random Variables .     . .  . . . . 169
A.8 Continuity of Probabilities . . . .   . .  . . . . 170
A.9 Exchanging Sums and Expectations .    . .  . . . . 171
A.10 Exchanging Expectations and Limits   . .  . . . . 172
A.11 Exchanging Limits and Sums . . .     . .  . . . . 173
A.12 Basic Linear Algebra . . . . . . .   . .  . . . . 174
A.13 Miscellaneous Math Facts . . . . .   . .  . . . . 175
B Bibliography for Further Reading                        177
C Solutions to Problems Marked [sol]                      179
Index                                                     197
```

The book A First Look at Stochastic Processes may be ordered from the publisher, or from e.g. amazon.ca or kobo. See also Jeffrey Rosenthal's research papers and home page.