An analysis of one-dimensional schelling segregation

Christina Brandt, Nicole Immorlica, Gautam Kamath, Robert Kleinberg

Abstract: Thomas Schelling's 1969 model of residential segregation is a cornerstone of social science, yet its unperturbed one-dimensional variant has long eluded rigorous mathematical analysis. This paper provides the first such analysis, proving that contrary to common intuition, the unperturbed model leads to a highly integrated society. By introducing novel techniques like "firewall incubators" and "taint coupling," the authors demonstrate that segregation remains local and independent of total population size.

Introduction: The Problem of Emergent Segregation

In 1969, economist Thomas Schelling introduced a famous model demonstrating how individuals with a mild preference for having neighbors of their own type can inadvertently cause massive global segregation. While easy to simulate, the model is notoriously difficult to analyze mathematically because the system can freeze in many different states, meaning the underlying Markov chain lacks a unique stationary distribution.

To get around this, previous researchers analyzed perturbed versions of the model—adding a tiny probability that agents make "mistakes" (utility-decreasing moves). These perturbed models inevitably drift toward complete, global segregation. This paper asks: what happens if we rigorously analyze the original, unperturbed model? Do agents strictly following Schelling's rules actually segregate globally, or does the lack of random noise lead to a different outcome?

Methodology: Firewalls and Taint Coupling

The authors model a society of $n$ individuals (of two types, $x$ and $o$, with equal probability) arranged on a 1D ring network. Each individual looks at a window of $w$ neighbors on either side and is "happy" if at least half ($\tau = 1/2$) are of their own type. In each step, two randomly chosen unhappy individuals of opposite types swap places.

To analyze this, the authors introduce several novel theoretical techniques:

  • Firewalls and Incubators: They define a "firewall" as a run of $w+1$ identical agents. Once formed, these agents are permanently happy and will never move. They then identify "firewall incubators"—specific initial configurations that have a high probability of evolving into firewalls.
  • Wormald’s Differential Equation Method: To prove that the number of unhappy $x$'s and $o$'s remains balanced throughout the process, they approximate the discrete random process with continuous differential equations.
  • "Taint" Coupling: Wormald's method usually fails here because a ring network creates infinite dependency chains (a swap in one place can eventually affect the whole ring). The authors bypass this by partitioning the ring into bounded-size pieces and tracking a "taint" variable to bound the error between the true ring and the partitioned approximation.
Figure 1: Visualization of the partitioning and 'taint' coupling used to analyze dependencies on the ring network.

Key Insights and Results

Unperturbed Dynamics Prevent Global Segregation

Without the random "mistakes" introduced in prior literature, the Schelling model quickly forms local "firewalls." These firewalls lock the grid in place, halting the cascading movement required to achieve massive global segregation. The final state of the society is surprisingly integrated. The size of a monochromatic (segregated) neighborhood depends only on the individual's vision radius ($w$), not on the size of the city ($n$).

Mathematical Breakthroughs

The "taint" coupling technique used to apply Wormald's method to a ring network is a significant contribution to discrete probability. It offers a new way to analyze random processes on large graphs where weak, long-range dependencies usually break standard differential equation approximations.

Summary of Results

  • Guaranteed Termination: As $n \to \infty$, the probability that the unperturbed process eventually reaches a frozen, stable configuration converges to 1.
  • Bounded Run Lengths: In the final frozen configuration, the average run length (the size of a segregated block) is $O(w^2)$.
  • Exponential Decay of Large Segregation: The probability of a randomly selected node belonging to a segregated run longer than $\lambda w^2$ is bounded above by $c^\lambda$ (where $c < 1$).
  • Balanced Unhappiness: With high probability, the number of unhappy $x$'s and $o$'s remains tightly balanced until the very end of the segregation process.

Limitations and Future Work

The analysis is strictly limited to a one-dimensional ring. Real-world residential neighborhoods are better modeled by 2D grids, which exhibit much more complex behavior and remain a massive open problem for rigorous mathematical analysis. Furthermore, the proofs rely heavily on the assumption that the initial population is exactly 50/50 and the tolerance threshold is exactly $\tau = 1/2$. The authors note that varying these parameters could lead to qualitatively different behavior (e.g., run lengths becoming exponential rather than polynomial). Finally, the authors conjecture that the true average run length in the final state is actually $\Theta(w)$, which is tighter than their proven upper bound of $O(w^2)$.

Summary updated

BibTeX
@inproceedings{brandt2012analysis,
  author = {Christina Brandt and Nicole Immorlica and Gautam Kamath and Robert Kleinberg},
  title = {{An analysis of one-dimensional schelling segregation}},
  booktitle = {STOC},
  year = {2012},
  url = {https://openreview.net/forum?id=yMR_7zLhh0b},
}
Figure