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 kobo. See the Preface and Contents below, the errata, and the related computer simulations.

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

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

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.