Abstract

Abstract: This lecture covered the differential equation method.  We first defined Wormald's Theorem, then applied it to calculate the distribution of bin sizes in a balls and bins process, and finally applied it to study the distribution of run lengths in a Schelling segregation model.  The talk was not recorded, but here are some resources if you would like to learn about these techniques:

1) My own lecture notes and slides.

2) "A Gentle Introduction to the Differential Equation Method and Dynamic Concentration" by Patrick Bennet and Andrzej Dudek on applying the differential equation method to a balls and bins process.  The first part of this lecture was based on Section 3.

3) "An Analysis of One-Dimensional Schelling Segregation" by Christina Brandt, Nicole Immorlica, Gautum Kamath, Robert D. Kleinberg (see also video of conference presentation), on applying the differential equation method to show that Schelling swap-style dynamics can be well approximated by flip dynamics for sufficiently long.  The second part of this lecture was based on Section 3.2 and Appendix A.3.