[Update June 2015: since I rebooted my site, the wallpaper uses a design which emerged from work George Barmpalias, I, and Andy Lewis-Pye did together on Schelling’s model of racial segregation. This post describes our research.]
I talked in the previous post about a model of racial segregation devised by Thomas Schelling in 1969 [original pdf]. This post will describe how the model works, in its simplest 1-dimensional incarnation, and what we’ve discovered about it. (I hope this post is also accessible to everyone, but I’ve included the formal statements for the more mathematically-minded reader.)
Schelling’s Model
Suppose that a large number of people, say a hundred thousand (or more generally 
), all live around the edge of a giant circle. This is the city. We’ll imagine that its citizens are of two races: red and blue. Initially we populate the ring randomly, meaning that we go around each house in turn tossing a coin to decide the colour of the resident.
Once all the people are in place, each person will only be concerned with their own immediate neighbourhood: say the 80 people to their left, and the 80 people to their right, making its total size 161. (The number 80 is the called neighbourhood radius, or 
, and as with we can alter it later.)
Now we have to factor in people’s preferences. Let’s imagine that each person is happy so long as they’re in the majority in their neighbourhood, but they’re unhappy if they’re in the minority. So, if some red individual’s neighbourhood contains 75 red people and 86 blues, she’ll be unhappy. But if contains at least 81 red people, including herself, she’s guaranteed to be happy, since the reds are bound to outnumber the blues. We’ll imagine that everyone feels similarly.
The idea is that unhappy people may then move house (while happy people won’t). To model this, at each time-step we pick, at random, a pair of unhappy people of opposite colours and swap them. This will have knock on effects on the neighbours of those two nodes, who may themselves change from being happy to being unhappy, or vice versa. We keep repeating this until we run out of unhappy people of one colour or other.[1]
Ok, those are the rules. And the big question is: what will the ring look like at the end of this process? And the answer is…
As you can see, distinct red and blue regions have developed. If we want to measure the level of segregation, we need to know how big these areas are.
The first rigorous answer to this question was provided in a recent paper by Christina Brandt, Nicole Immorlica, Gautam Kamath, and Robert Kleinberg. They prove, roughly speaking, that the segregated regions are not significantly bigger than the original neighbourhoods.
More technically, their theorem says this: for any 
, for all and all sufficiently large , the average length of the segregated regions is 
with probability at least 
. (They conjecture that this can be further tightened to 
.)
Altering the Tolerance
Here’s a new question: what might happen to this picture if we tweak the system to make people more tolerant? Instead of requiring their own colour to be a majority in their neighbourhood, perhaps they’re happy so long as it’s not below 38%, say. Well, this is the picture that emerges if we set the tolerance parameter 
…
This is, I hope you’ll agree, a rather surprising turn of events. After all, one might naively expect that if people are content with a greater level of mixing, this should be reflected in their final arrangement. But what we’re actually faced with are dramatically larger segregated regions.
In more technical terms the segregated regions have jumped from being polynomial (or conjecturally linear) to being exponential relative to the neighbourhood radius.
In even more technical terms, in our paper, Andy Lewis-Pye, George Barmpalias and I prove that in this situation there exists a number 
such that for any and for all 
(meaning “for all sufficiently large and all sufficiently large compared to ”), the probability that a randomly chosen node will end up in a segregated region of length greater than 
is greater than 
.
Why should this be? Well, we get a hint if I add in some extra information to the pictures. Here’s the first scenario again, where the tolerance is 
:
The innermost ring is the city’s initial configuration. Outside that are markers for the initially unhappy nodes. Then the body of the ring shows the changes which take place over the course of the run, with distance from the centre proportional to when the change happened. At the outside is the result: the same final configuration we saw before. Now let’s have another look at the case where :
In this case, there are visibly fewer initially unhappy nodes. But each of them sets off a domino effect: when they change, the nearby nodes of the same colour become unhappy, and so on. Paradoxically, because almost everyone is initially happy, the resulting firewalls can extend much further before running into each other, which is how the larger segregated regions are formed.
A Threshold Between Segregation and Integration
What if we make people even more tolerant? Suppose 
, which is to say people are happy so long as at least 30% of the neighbourhood are their own colour.
As you can see, there’s not a lot going on here; now everyone is initially happy, and remains that way. In our paper, we show that the threshold value is (kappa approx 0.353092313 ). More precisely, for those who are interested, it is the root of the following equation[2]:
For values of 
above this threshold, but below 0.5, the theorem above applies (though the value of 
will vary). For values below 
, the ring will be static or nearly so. More precisely, we prove that for any for any and for all 
, the probability that a randomly chosen node changes colour at any point is less than 
.
This threshold manifests itself very dramatically when running simulations: below it very little happens. Then… boom!
Moving To Total Segregation
Finally, you might wonder what would happen if we make people less tolerant. Perhaps everyone requires their neighbourhood to contain at least 65% of their own colour, meaning 
. In this situation, common-sense suggests that we should see higher levels of segregation, and this time case common-sense gets it right, though the change is again more dramatic than one might have guessed:
(This ring has 
.)
In fact, the point 0.5 is another crisp threshold: whenever exceed 0.5, so long as is large enough, complete global segregation is inevitable sooner or later [3].
[1] Actually what I’ve described is the closed model. There’s an even simpler open model in which we pick at each stage a single unhappy node and change its colour – we might imagine that the unhappy red resident has moved out of the city altogether and been replaced by a blue resident whose moved in from elsewhere. One challenge is to determine to what extent the open model is a reasonable approximation to the closed one.
[2] If you know anything about this number, please let me know!
[3] In this case we adopt the additional convention that someone will refuse to swap if they will be less happy in their new position than in their current one. Also notice that in this case, the process never fully terminates, as the people on the edges of the segregated regions will remain unhappy. But the only thing that can happen after complete segregation has occurred is that the boundaries of the regions shuffle a little this way and that.
Simple City 