  We analyze the Schelling model of segregation in which a society of n
individuals live in a ring. Each individual is one of two races and is only
satisfied with his location so long as at least half his 2w nearest neighbors
are of the same race as him. In the dynamics, randomly-chosen unhappy
individuals successively swap locations. We consider the average size of
monochromatic neighborhoods in the final stable state. Our analysis is the
first rigorous analysis of the Schelling dynamics. We note that, in contrast to
prior approximate analyses, the final state is nearly integrated: the average
size of monochromatic neighborhoods is independent of n and polynomial in w.
