Applied Stochastic Processes

Course Description

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

1. Fundamental tools and methods: Basic concepts (integration, transforms, inequalities, convergence) and more advanced probabilistic tools (coupling and stochastic ordering, martingales, renewal theory, spectral methods).

2. 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:

1. Fundamental Probabilistic Models: Balls and bins, the Galton Watson branching process, the Erdos-Renyi graph, queueing networks, epidemics and percolation.

2. Algorithmic Applications: Basics of randomized algorithms, the probabilistic method, Monte Carlo simulation and sampling, applications in distributed algorithms, data sketching, optimization and machine learning.

• Course Syllabus

Course Information

• Lectures: MWF 12:20-1:10pm, Phillips 213

• Instructor: Sid Banerjee, 229 Rhodes Hall, email

• 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).

References

The course will primarily be based on the following two textbooks (both by Pierre Bremaud):

1. Discrete Probability Models and Methods (for majority of topics)
2. Markov chains: Gibbs fields, Monte Carlo simulation, and Queues (for CTMCs) An e-copy of the book is available on the Cornell library website, which also gives you access to a low-price MyCopy edition from the Springer website.

A few other excellent references, with significant overlap in terms of topics and technical level:

• Probability and Random Processes by Grimmett and Stirzaker
• Adventures in Stochastic Processes by (our very own!) Sid Resnick
• Random Processes for Engineers by Bruce Hajek

References for topics in randomized algorithms and combinatorics:

• Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
• Probability and Computing by Michael Mitzenmacher and Eli Upfal
• The Probabilistic Method by Noga Alon and Joel Spencer

Lecture Notes

• 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]