Segregation Models
Nicole Immorlica (Microsoft Research)
Calvin Lab Auditorium
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.
Attachment | Size |
---|---|
differentialequationmethod.pdf | 120.45 KB |
schelling-simons.pdf | 1.35 MB |