About the summer school

This summer, as a pilot program, SNAPP is running a virtual summer school. This is a virtual lecture series held on Zoom with the aim of teaching an advanced but broadly applicable topic to researchers in applied probability.

For the inaugural summer school, we are delighted to have Anton Braverman (Northwestern University) teach a 10-lecture course about Stein's method for queueing approximations. Lectures will be recorded and posted to the SNAPP YouTube channel.

If you're planning to attend, please fill out the brief interest form. See below (and this spreadsheet) for a schedule and course description, and sign up for the SNAPP mailing list to stay tuned for updates.

Course Description

The generator comparison approach of Stein’s method is a framework used to compare the stationary distributions of any two Markov processes and derive bounds on their distance under some integral probability metric. Notably, the approach does not require coupling the two distributions.

Roughly ten years ago, the generator approach was introduced to queueing theory and, specifically, to the area of fluid and diffusion approximations of queueing models. The ability to compare the steady-state distribution of the fluid/diffusion approximation to the original (often intractable) queueing model spurred a variety of interesting research questions. The past ten years have provided answers to many of these questions. Some highlights:

• We now have a theory to derive rates of convergence of the original queueing model to its diffusion/fluid approximation

• We now know that diffusion/fluid models can perform well universally, across multiple parameter regimes (as opposed to heavy-traffic limit theorems which assume that the model primitives converge to one particular limit; e.g., the Halfin-Whitt regime).

• We have learned of higher-order approximations whose approximation error goes to zero an order of magnitude faster than “classical” approximations

• The generator approach has been extended to the setting of dynamic control (MDPs) where it quantifies the error of approximating an MDP by the continuous Brownian control problem, resulting in an approximate DP state-space aggregation algorithm.

• The generator approach has been extended to “non-Markovian” models; e.g., queueing models with general inter-arrival and service time distributions.

The purpose of this course is to disseminate the developments in the generator approach (with a focus on queueing) over the past ten years. No prior knowledge is assumed. We begin with the basic generator approach for a simple one-dimensional birth-death process, and then add complexity by considering multidimensional CTMCs and, eventually, piecewise-deterministic Markov processes where jumps are driven by general clocks.

At the end of the course students will be familiar with using the generator approach and will be able to apply it to their own research. They will also know the state-of-the-art of the theory, including some open problems.

Prerequisites

The target audience is graduate students, postdocs, and faculty working in applied probability, but there are relatively few specific prerequieites. Participants should be familiar with CTMCs (positive recurrence, stationary distributions). Familiarity with Ito’s lemma is a plus, but it will be reviewed at the start of the course.

Syllabus

1. Preliminaries: Ito’s lemma, generators of CTMCs and diffusion, and the drift method.

2. A simple one-dimensional example: the M/M/∞ queue.

3. High-order diffusion approximations.

4. The prelimit generator comparison approach.

5. Multi-dimensional examples: state-space collapse and gradient (Stein factor) bounds.

6. Beyond CTMCs: applications to models with generally-distributed jump clocks.

You can view a lecture-by-lecture topic schedule here. Time permitting, additional topics may include Stein’s method for mean-field approximations and Stein’s method for MDPs/dynamic control.