This is a graduate course which aims to provide a non measure-theoretic introduction to stochastic processes, presenting the basic theory together with a variety of applications. Students are assumed to have taken at least a one-semester undergraduate course in probability, and ideally, have some background in real analysis. We will focus on the following primary topics
Fundamental tools and methods: Basic concepts (integration, transforms, inequalities, convergence) and more advanced probabilistic tools (coupling and stochastic ordering, martingales, renewal theory, spectral methods).
Markovian models: Discrete-time Markov chains, recurrence and transience, invariant distributions, the ergodic theorem, reversibility, Lyapunov functions, Markov chain mixing, Poisson processes and continuous-time Markov chains.
In addition, we will illustrate these tools with applications in a variety of settings, depending on time and student interest:
Fundamental Probabilistic Models: Balls and bins, the Galton Watson branching process, the Erdos-Renyi graph, queueing networks, epidemics and percolation.
Algorithmic Applications: Basics of randomized algorithms, the probabilistic method, Monte Carlo simulation and sampling, applications in distributed algorithms, data sketching, optimization and machine learning.
Lectures: MWF 12:20-1:10pm, Phillips 213
Piazza and CMS: Please ensure you are signed up on the Piazza site site for all course announcements and material. In addition, for submitting assignments (and also grading), we will CMSX (you will be added once class starts).
The course will primarily be based on the following two textbooks (both by Pierre Bremaud):
A few other excellent references, with significant overlap in terms of topics and technical level:
References for topics in randomized algorithms and combinatorics:
Set 1: Probability basics [notes]
Set 2: Conditional expectation [notes]
Set 3: Convergence of random variables [notes]
Set 4: The Probabilistic Method and Measure Concentration [notes]
Set 5: Introduction to Markov Chains [notes]
Set 6: Markov Chain Convergence and Mixing Times [notes]
Set 7: Martingales [notes]
Set 8: The Poisson Process [notes]
Set 9: Continuous-Time Markov Chains [notes]