SELECT * FROM Celko – September 2013

“The interplay of individual choices, where unorganized segregation is concerned, is a complex system with collective results that bear no close relation to the individual intent.” 
— Thomas C. Schelling – 1969. 
The Department of Housing and Urban Development is imposing a new rule that would allow the government to track diversity in neighborhoods across the country and then push policies to change those it deems discriminatory. The policy, called “Affirmatively Furthering Fair Housing”, would require the agency to gather data on segregation and discrimination in every neighborhood and try to remedy it. 
This remedy is coming from the same people who tried to remedy the housing problem with a sub-prime, no down payment policy and tons of Federal money for social engineering. We all know how well that worked. This is not just bad policy, but this is mathematically absurd. 
Today, we play video games in imaginary worlds where you are in complete control. Not many of us keep a giant killer robot in the garage to stomp the countryside. But more than that, these simulations can have their own physics and behaviors that have nothing to do with reality. 
The pure mathematical ancestors of these video games are called cellular automata. Us older programmers remember John Conway’s Game of Life as a popular programming assignment in the 1970’s. You are given an infinite grid of squares and some imaginary creatures that I call Merkles that we represent with a dot in some of the squares. 
Every Merkle interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
  1. A Merkle with fewer than two neighbors dies from loneliness and disappears from the next generation. 
  2. A Merkle with two or three neighbors lives on to the next generation.
  3. A Merkle with more than three neighbors dies from overcrowding.
  4. Any empty cell with exactly three live neighbors grows a Merkle. 
The Wikipedia write up on this has animations that are fun to look at.

For us databases guys, we know that this is where Dr. Codd started before he invented the Relational Model. If you want to read it, you can download it at

Did you ever hear of the an economist Thomas C. Schelling? He created a simple artificial neighborhood to study a generation ago. His observation was how real segregated neighborhoods behaved in his day.

His model world is a square grid and the citizens are either Red Merkles or Blue Merkles. Every square has a Merkle living there. We fill Merkleville randomly with an equal number Red Merkles and Blues. Dr. Schelling did not use a computer when he started playing with this model, but we have an advantage over him today.

We need a happiness rule for Merkleville. This rule is simpler than Life; every Merkle wakes up and looks North, South, East and West to see his neighbors. If he is in a corner or on a edge, do a wrap-round, making Merkle-world a torus. If a Merkle exits to the right, it reappears on the left, and if it exits at top, it reappears on the bottom.

Now, we need a the happiness rule. A Merkle is happy only if its four neighbors (this is called an Ulam neighborhood) include at least (n) Merkle of his own color. Any two unhappy Merkles can swap, if they both increase or maintain their happiness. There is no cost to moving, no restrictive covenants, no neighborhood associations (aka “Lawn Nazis”) or other examples of nosy neighbors running your life. This is a pure abstract model.

This actually gives us a way to model the net happiness of Merkleville by summing the score of all the Merkles. Another cute programming exercise!

We could start with ‘colorists’ Merkles that want to live in pure district where (n = 4) district. Very quickly, Red Merkles gravitate to solid red districts, and Blue Merkles gravitate to solid blue districts. Once the districts are established, the border between the districts shifts a little as Red Merkles and blue Merkles jockey to move away from the boundary. This feels right, so it is not a great surprise.

Let’s do some “Affirmatively Furthering Fair Housing” in this model. Let’s program perfectly tolerant Merkles who seek only ( n < = 2 ) neighbors of his own color. This is the Department of Housing and Urban Development’s magical population of Merkles who are free of any desire for segregation and discrimination. They seek an integrated district, half red, half blue. My Merkles seek mathematically pure diversity without a Federal Marshal pointing a gun at them or any economic restrictions.

Write and run your program. The individual preferences of your Merkles will produce a collective outcome indistinguishable from a colorist housing policy. The differences are the speed that it takes to get to the segregation.

You get discernible colored clusters, then the boundaries harden. The Merkles would be perfectly happy to be in the minority; they want only to avoid being completely alone.

You can see some QuickTime animations of Merkleville at these sites:

For (n = 2)

For (n = 1)


submit to reddit

About Joe Celko

Joe is an Independent SQL and RDBMS Expert. He joined the ANSI X3H2 Database Standards Committee in 1987 and helped write the ANSI/ISO SQL-89 and SQL-92 standards. He is one of the top SQL experts in the world, writing over 700 articles primarily on SQL and database topics in the computer trade and academic press. The author of six books on databases and SQL, Joe also contributes his time as a speaker and instructor at universities, trade conferences and local user groups. Joe is now an independent contractor based in the Austin, TX area.