Course Outline

Modeling large and complex systems requires reasoning about probabilistic behavior at a large scale. This course covers fundamentals of probabilistic system modeling, building towards techniques that allow analyzing complex stochastic systems in a tractable fashion. The course will review classic topics like Markov chains, convergence to a steady state, and renewal processes, as well as advanced topics such as renewal reward processes, the strong law of large numbers and the elementary renewal theorem, the asymptotic behavior of probabilistic systems, including stochastic approximation/Robbins-Monro type algorithms and ODE/fluid limits. Throughout the course, examples will illustrate how such techniques can be applied to reason formally about several applications, including queueing systems, network congestion, distributed storage systems, as well as online learning algorithms such as stochastic gradient descent.

Blackboard Site

Syllabus

• Review of Bernoulli, Poisson and general renewal processes.
• Strong law of large numbers for renewal processes. Renewal reward processes, stopping rules, the elementary renewal theorem, and Blackwell's theorem.
• Review of Markov chains and processes: ergodicity, reversibility, and convergence to steady state.
• Rates of convergence and mixing times; random walks, relaxation time, and expander graphs.
• Foster-Lyapunov stability criteria.
• Analysis of dynamical systems through fluid limits: stochastic approximation algorithms, the ODE method, and mean-field analysis.

Resources

Textbook: Stochastic Processes, R. G. Gallagher
Additional Resources:

• Reversible Markov Chains and Random Walks on Graphs, D. Aldous and J.A. Fill, available online.
• Adaptive Algorithms and Stochastic Approximations, A. Benveniste, M. Metevier, P. Priouret.
• Stochastic Approximation: A Dynamical Systems Viewpoint, V.S. Borkar.