[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.

When a city contains people of different races, segregation often occurs: sizeable parts of town largely inhabited by people of one race. But when asked what sort of neighbourhood they would like to live in, people often report a preference for mixed neighbourhoods. So why does the reality often fail to reflect this desire?

Of course, there are various conceivable explanations. One comes from what economists call revealed preferences, meaning that, when push comes to shove, people may not be quite so keen on mixed neighbourhoods as they thought they were. But there are other, more interesting possibilities. With some friends I’ve recently being doing some mathematical work which is relevant to this question, and which allows us to take people at their word. The interesting thing is: high levels of segregation can emerge even in a city where everyone would be completely happy in a mixed neighbourhood.

It also produces some rather lovely pictures:

In the next post I’ll explain what this picture means and discuss our work in more detail. (Impatient? The preprint is here.) This post is background, and the starting point is a theoretical model of racial segregation devised by Thomas Schelling in 1969. It’s a simple model of a city, in which people may move houses depending on whether or not they are satisfied with the make-up of their current neighbourhoods.

Schelling is best known for his infamous work on game theory at the RAND Corporation during the Cold War. His book on that subject, Strategies of Conflict, is a very readable introduction to these ideas (so long as you don’t mind a little maths), and is accurately summarised by Cousin It as follows:

”Forget rationalist Judo: this is rationalist eye-gouging, rationalist gang warfare, rationalist nuclear deterrence. Techniques that let you win, but you don’t want to look in the mirror afterward.”

Schelling also played an interesting role in the genesis of Stanley Kubrick’s film on this very subject: Dr Strangelove (Or: How I Learned To Stop Worrying And Love The Bomb).

In 2005, Schelling was awarded the Nobel Memorial prize in Economics in 2005 (though not without some controversy). The Academy commented on both his work on strategy and – my focus here – his insights into questions related to racial segregation.

I’ll describe his model in the next post, but as you will see it is very simple indeed. Now, you can view this either as a good or a bad thing. For a mathematician – that’s me – it’s good, since it provides the possibility of a thorough analysis of the mechanisms at work. On the other hand, for a social scientist, it does carry the undeniable disadvantage that the model is a pretty feeble reflection of reality.

So let’s admit from the outset that Schelling’s model town is by no means realistic: it ignores obviously relevant factors such as geography, local amenities, transport, and, well, pretty much anything else you can think of that real people actually care about when choosing where to live. On top of this, it pretends that people live in a beautifully convenient geometrical arrangement, which in reality happens only occasionally.

There have been numerous subsequent modifications of the model to make it more realistic, and therefore presumably more useful to social scientists, for instance by incorporating factors such as house prices. Even so, I hold that Schelling’s original simple model carries a rather profound lesson for us all, not about racial segregation particularly, but more generally about the relationship between the actions of individuals and the larger scale social structures to which they can give rise.

This relationship can be extremely counterintuitive, as discussed in Schelling’s – again very readable and less technical – book on this theme: Micromotives and Macrobehaviour. As he says

“…sometimes the results are surprising. Sometimes they are not easily guessed. Sometimes the analysis is difficult. Sometimes it is inconclusive. But even inconclusive analysis can warn against jumping to conclusions about individual intentions from observations of aggregates, or jumping to conclusions about the behavior of aggregates from what one knows or can guess about individual intentions.”

In particular, in the next post I’ll discuss the surprising finding that when people are more tolerant of neighbours of different races, this may actually lead to greater segregation.