Simple City  

I talked in Part 1 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 \(n\)), 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 \(w\), and as with \(n\) 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 \(\epsilon>0\), for all \(w\) and all sufficiently large \(n\), the average length of the segregated regions is \(O(w^2)\) with probability at least \(1-\epsilon\). (They conjecture that this can be further tightened to \(O(w)\).)

 

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 paramater \(\tau=0.38\)…

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 \(d>0\) such that for any \(\epsilon > 0\) and for all \(n \gg w \gg 0 \) (meaning “for all sufficiently large \(w\) and all \(n\) sufficiently large compared to \(w\)”), the probability that a randomly chosen node will end up in a segregated region of length greater than \(e^{\frac{w}{d}}\) is greater than \(1 – \epsilon\).

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 \(\tau=0.5\):

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 \(\tau=0.38\):

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 \(\tau=0.3\), 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]: \[ \left( \frac{1}{2}-\kappa \right)^{1-2\kappa} = \left( 1-\kappa \right)^{2-2\kappa} \]

For values of \(\tau\) above this threshold, but below 0.5, the theorem above applies (though the value of \(d\) will vary). For values below \(\kappa\), the ring will be static or nearly so. More precisely, we prove that for any for any \(\epsilon > 0\) and for all \(n \gg w \gg 0 \), the probability that a randomly chosen node changes colour at any point is less than \( \epsilon\).

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 \(\tau=0.65\). 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 \(n=10,000, w=20, \tau=0.65\).)

In fact, the point 0.5 is another crisp threshold: whenever \(\tau\) exceed 0.5, so long as \(w\) 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.

Here’s a question:

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.

 

Yesterday, two – yes two! – dramatic developments in the theory of prime numbers were announced. Both are – if correct – major theorems in their own right. Both can also be seen as steps towards the very biggest questions in the subject.

(For those who came in late: remember that a prime is a whole number like 7, which can’t be divided by anything except itself and 1. So 6 is non-prime as it is divisible by 2.)

 

Twin Primes

It has long been observed that prime numbers sometimes come in pairs: 3 & 5, 17 & 19, 29 & 31, 821 & 823,…

The Twin Prime Conjecture asserts, very simply, that this list goes on forever: there are infinitely many pairs of twin primes, meaning pairs \(a\) and \(b\) where \(b=a+2\). This is an old open problem which has left numerous clever people scratching their heads down the centuries. Although the list of known twin primes has grown ever longer (as of 2013, the record holders are 200700 digits long!), no-one has managed to prove it for certain.

Yesterday at Harvard Yitang Zhang announced a proof, not of the full twin prime conjecture, but of a weaker result: that there are infinitely many pairs of primes \(a\) and \(b\) where \(a < b \leq a+70,000,000\). Although this bound of 70 million is admittedly slightly bigger than 2, this is still a huge breakthrough, as it is the first time any result of this type has been proven. It establishes for the first time a very deep fact indeed: that even when you look at truly gigantic primes, you are guaranteed still to find some which are close together in an absolute and unwavering sense.

 

Goldbach’s Conjecture

In a letter to Leonhard Euler in 1742, Christian Goldbach remarked that every even number bigger than 2 can be written as two primes added together: e.g. 4=2+2, 10=7+3, 100=61+59, etc..

Again, a great many people have tried and failed to prove that this simple observation should always hold, although (again) computational work has verified it for all even numbers up to a large value, in this case 4,000,000,000,000,000,000.

Now, another way to state Goldbach’s conjecture is to say that every whole number from 7 onwards (not necessarily even) can be written as the sum of three primes. (It’s worth spending a minute or two thinking about why this is equivalent.)

A weaker statement, then, is that every odd number from 7 onwards is the sum of three primes. This statement, known as Goldbach’s Odd Conjecture, would certainly follow from his main conjecture. But it looks as if we won’t have to wait that long, because yesterday Harald Helfgott claimed a proof!

In fact, Helfgott has shown that it is true for all odd numbers above 10,000,000,000,000,000,000,000,000,000,000, and separately with David Platt has checked numbers up to that limit by computer.

In fact, we’ve known since 1937 that Goldbach’s Odd Conjecture must hold for all large enough numbers, but previously the threshold was over 1300 digits long: way, way too big to be checked computationally. Yesterday, Helfgott finally slammed that window shut.

[Post edited 15th May, see comments]

UPDATE, 19th May. In fact, Peter Rowlett points out that Helfgott is claiming the proof of two weak Goldbach conjectures:

1) Every odd number from 7 onwards is the sum of three primes

and the stronger statement:

2) Every odd number from 9 onwards is the sum of three odd primes (i.e. you can do it without using 2).

In a paper with the unassuming title of Inter-universal Teichmuller theory IV: log-volume computations and set-theoretic foundations [pdf], Shinichi Mochizuki has released a purported proof of the ABC conjecture. This would be huge news if correct, as this single conjecture is known to imply all sorts of exciting facts about the world of numbers. Proposed by Joseph Oesterlé and David Masser in 1985, its most famous consequence is Fermat’s Last Theorem… but of course that has already succumbed to other methods. So, to give a flavour of its power, I’ll discuss another: Pillai’s conjecture.

This starts with the observation that the numbers 8 & 9 are rather unusual. They are neighbours which are both powers of other positive whole numbers: 8=2³ and 9=3². In 1844, Eugène Catalan conjectured that this is the only instance of two powers sitting next to each other, a delightful and surprising fact which was eventually proved by Preda Mihăilescu in 2002.

However, a host of related questions remain unanswered. What about powers which are two apart, as 25 (=5²) and 27 (=3³) are? Or three apart, as happens for 125 (=5³) and 128 (=2⁷)?

In 1936 Subbayya Pillai conjectured that for every whole number k there are only ever finitely many pairs of powers exactly k apart. But so far the only case this is known is for k=1, i.e. Catalan’s original 8 & 9.

A proof of the ABC conjecture would confirm Pillai’s conjecture for all the remaining values of k at a stroke… and a great deal else besides. So watch closely as the world’s number theorists now descend on Mochizuki’s paper!

I’ve an article in the current edition of the New Scientist, about linear programming, convex polytopes, and Santos’ recent refutation of the Hirsch conjecture.

It’s available online here (£) or in a newsagent near you, presuming you live somewhere where the New Scientist is sold…

This is a sequel to the first hat game post, please read for the background. Everything here is based on a recent talk by Robert Lubarsky, about work of his with Stefan Geschke, though any errors are mine. This post will end up with some unsolved questions: if you think you know the answers (either because you can solve them yourself, or you know where solutions can be found), please leave a comment here or drop Robert an email. (He told me he was quite happy to throw this material out into the public domain, and I would obviously be delighted if this blog helps find some answers!)

So… the basic puzzle in this post is as before, but this time the first person in line sees an infinite queue of hat wearers standing in front of him. What strategy can our team adopt, to maximize the number of hats they are able to name correctly? Have a think about it… and a discussion follows this picture:

 

 

Hats and Tails

 
Last time we started representing our hat-wearers using binary sequences, that is strings of 0s and 1s. The new puzzle plunges us into a world of infinite binary sequences. Infinite things are generally not easy to write down, so let’s take a very simple example consisting only of ones:
A = 1111111111111111……..

We’ll say that two infinite binary sequences are equivalent if they share the same tail, meaning that are identical beyond some point, before which they may differ (or to put it another way, the two only differ in finitely many places). So the sequence A above is equivalent to B = 0010111111111111……..

This notion of equivalence divides the whole space of all possible binary sequences into ‘classes’, inside each of which all sequences are equivalent. Getting back to our hat-wearing friends, everyone in the line has infinitely many people in front of them, and only finitely many behind. So everyone can tell at a glance which class they are in. They all know whether or not they are equivalent to A, or to any other specified sequence.

This doesn’t immediately help them. But we can take it a little further. We say two sequences are evenly equivalent if they differ in an even number of positions. Obviously, if two sequences are evenly equivalent, then they are equivalent. But not vice versa: A and B are equivalent but not evenly so.

A little thought reveals that any sequence which is in the same class as A (and therefore B) must be evenly equivalent to either A or to B. (Think about it!) Now this really is a useful fact for the hatters to exploit. In their strategy-meeting before the game, they go through every class, and they select one special sequence from it, to act as a reference point. Let’s say, for the class containing A & B, they choose A.

When they come to line up, let’s suppose the sequence of hats which emerges is B = 0010111111111111…….. Now, everyone can see which class they are in. So everyone knows to follow the plan and compare their own sequence to A. But they do not know which subclass they’re in i.e. whether they are evenly equivalent to A. However, the first person (who is hatless in this version) can see the whole sequence. So she can discern the subclass, in particular she sees that the sequence is not evenly equivalent to A. So she calls out “1”. (It would have been “0”, had the sequence been evenly equivalent to A.)

Now, as far as the next person is aware, the sequence is X010111111111111…….. where X is his own hat colour. He doesn’t know the value of X, but he knows from what he hears over his shoulder that the overall sequence is not evenly equivalent to A. So, he deduces that X=0, which he calls out. The next person knows 0Y101111111111….., and that the whole sequence is not evenly equivalent to A, so concludes that Y=0, and so on.

 

Millinery Strategists

 
So our team has its strategy. The nub of it is to use the meeting beforehand to select one special sequence from every class, to which they will then compare their own via even equivalence. Call this strategy 1.

In fact, strategy 1 is overkill. The players don’t need to specify an individual sequence from each class. All they really need to select is one of the two subclasses. Of course, a unique sequence gives you a subclass (`the subclass containing A’), but not vice versa. Strategy 2 is to go through all the possible classes of sequences, selecting one subclass from each.

To put this into action, the first person will call “0” if the sequence is in the selected subclass, and “1” if it’s in the other. The next player now knows which subclass they’re in. Combining that with what he can see will tell him his hat-colour, and so on.

There is also a third possible strategy: the players use their meeting to decide upon a non-principal ultrafilter on the natural numbers. (I won’t go into further details here, people who care about such things can fill them in themselves.)

 

The Superpower to Choose

 
We have arrived at three solutions to the puzzle. But there are further questions: which strategy is the easiest? And what superpowers do the players need to follow it? Leaving aside their infinitely good eyesight, hearing, mental acuity, and patience, each strategy gives them a job to do during their planning meeting. These tasks are not at all straightforward!

In the example above, A is a very easy-to-describe sequence. Most sequences are not like this, but are uncomputable, random, and generally indescribable. In general, there is no procedure or algorithm that the players can hope to use to pick out a single sequence from each class, as strategy 1 requires. This can only be done using a superpower, meaning some version of the axiom of choice. But full choice is certainly excessive, and there is an assortment of weaker axioms. What is actually required here?

Strategy 2 appears slightly easier than 1: the players don’t have to select one sequence from the infinitely many in each class, they just need to pick one of the two subclasses. Nevertheless Lubarsky & Geschke have shown that this still requires more choosing-power than comes freely with the ZF axioms. What is more, strategy 2 is minimal: any strategy which solves the puzzle will allow a subclass to be selected from each class. Together these two facts imply that a team of hat-wearers working purely within ZF cannot solve the problem, but one with the full power of ZFC can. What is the minimum superpower, in terms of ability to choose, that the players need for each strategy?

We know from the above remarks that strategies 1 and 3 are each at least as strong as strategy 2. The conjecture here is that they are both strictly stronger than 2, and what is more that 1 & 3 are themselves inequivalent. Any further thoughts?

Yesterday I heard a great talk by Robert Lubarsky, which provided a delightfully easy route into fairly deep logical waters. He was talking about joint work of his with Stefan Geschke.

This is the first of two two posts about it, each based around a puzzle. So let’s get going with the first, which is something of a classic. The second is altogether trickier, indeed a complete answer seems to be as yet unknown…

Here’s the first puzzle: ten (or a hundred or any number) people stand in a line, one in front of the other. Each is wearing either a black or a white hat. If you’re in the queue, you don’t know your own hat-colour, or those of the the people behind you. But you can see the ones in front. Starting from the back of the line, the challenge is for each person to call out in turn, trying to guess the colour of their own hat. They are allowed to discuss strategy beforehand. So what plan can they hatch to maximise the number of right answers?

Here is one possibility: the first person says the colour of the hat directly in front of him. So the second knows her hat colour, which she calls out. The third person then does the same favour for the fourth, and so on. This way, the team are guaranteed to get half the hats right. (We only care about guaranteed correct answers in this game, not lucky guesses.) In fact, there is a much better strategy. If you don’t know the answer, have a think about it now. The solution is on the other side of this picture.

Here’s an answer: the person at the back counts the number of black hats in front of him. If that’s an odd number, he says “black”. If it’s even, he calls “white”. Now, the next person can see all the same hats the first could see, except her own. Say she sees 5 black hats, and hears “black”. Can her own hat be black too? No, because otherwise that would make 6 black hats in front of the first person, an even number. So she knows her own hat must be white. Similarly, if she hears “white” then she knows that her own hat must be black. All the people in front can work out their own hat in the same way, by combining what they can see with what the people behind have said.

Now, this strategy allows everyone to discover their own hat colour, except for first the very first person. It is easy to see this is the best that can be done: no-one can see the first hat, so any tactic the team try will be immune to a change in its colour. To avoid this exception, in the next post we’ll assume the person at the head of the queue is hatless.

To set things up for the next post, I’ll write this another way, using “1” to represent black and “0” for white. So the sequence of hats might read 0010001111. The first person sees the whole sequence, adds up all the digits to get 5, and says “1”. (This is the total modulo 2, if you like.). The second person sees 010001111, and so on, with everyone seeing the same binary sequence, but with the beginning chopped off in different places.

I hope you agree that this hat game is a fun puzzle, with a neat answer. Its solution uses what computer scientists call a parity bit, a technique used to guard against data becoming corrupted.

In the next post things will become a little more serious, when we allow the queue of hat-wearers to grow infinitely long. In this new version, we have to assume that the hatters have various superpowers: they can see infinitely far in front of them, for example. It is obvious that the same tactic will not work in this setting, since everyone is likely to see infinitely many black hats in front of them (and of course it makes no sense to ask whether ‘infinity’ is odd or even). So what is the optimal result here, and what strategy will produce it? And, critically, what further superpowers do the people need to enact it?

Update: the second post is here.

I meant to post something about John Derrick, a long-standing and much loved member of the logic group at Leeds University, who died in December. I only knew John in his later years (some time after his official retirement), but would regularly see him at the Wednesday afternoon logic seminar, which was often followed by a trip to the pub. He was always a thoughtful and benevolent presence in the seminar room, and made for entertaining and knowledgeable company over a drink.

For younger members, he was also something of a link to an earlier era, the days when the group was led by Martin Löb (of Löb’s theorem fame).

It is a testamant to his strength of character, and his love of the subject, that he continued to attend and contribute to these seminars through many year of ill-health, up until only a few weeks before his death.

An obituary by Garth Dales appeared in the LMS news-letter and a longer one can be read on the University of Leeds website.

Pick’s theorem is a simple, beautiful, and usful fact of elementary geometry. It should be much better known than it is! In fact, I have half a mind that it should be on the A-level (high school) syllabus.

Less famous – but equally wonderful – are Ehrhart polynomials, which are what you get when you try to lift Pick’s theorem into higher dimensions. Though geometrically intuitive, they quickly lead into deep mathematical waters. They’re also valued as tools in optimisation problems and in other areas of computer science (I’m told).

This afternoon I gave a – hopefully fairly accessible – talk on these topics. The slides are available here.

(Update: PDF of slides here).