COMPUTING SCIENCE

# Small-Town Story

# A Random Walk on the Prairie

Population change has two components: natural increase (the excess of births over deaths) and migration (the number of people moving in minus the number moving out). For the purposes of this article, however, I shall ignore natural increase altogether and pretend that total population is a conserved quantity. Thus only migration matters, and one town's gain is necessarily another's loss.

The simplest of all migration models sets people wandering randomly from place to place. But what does it mean, exactly, to move randomly? Here's one algorithm: From the set of all towns, choose one in such a way that every town has the same probability of selection; call the chosen town the source, *S*. Now pick a second town, the destination, *D*, in the same way. Move one person from *S* to *D*. (Occasionally *S* and *D* will turn out to be the same place, but that's okay.)

When you repeat this process many times, what happens? Looking at the distribution of places according to size, the result is more realistic than we have any right to expect from such a primitive model. In round numbers, the U.S. has 20,000 incorporated places, which are home to 250 million people. If that population sorted itself out according to the algorithm above, the largest cities would have roughly 100,000 residents, and a fifth of all the places would be villages of 1,000 people or less. The actual distribution is steeper—with bigger big cities and more small towns—and yet the overall shape is similar. Even this partial success is something of a surprise, because the underlying assumptions of the model are quite implausible. In choosing a source or destination, it assigns the same probability to a North Dakota hamlet as to New York City.

A remedy for this distortion is to weight the probability of selecting each town according to its population. An equivalent way of formulating the same process is to choose a person—rather than a town—randomly and with uniform probability. The selected person will be the migrant. Now choose a second person in the same way, and let the migrant move to wherever this second person resides. Under this procedure, people everywhere have the same probability of moving, which is surely closer to the truth than the heavily biased scheme of the first model. But now another peculiarity turns up. If the population of a town ever falls to zero, that place can no longer be chosen either as a source or as a destination; in effect it is permanently removed from the model. What's more, such extinctions are inevitable. If you track the evolution of any one town's population, it executes a random walk on the integers, moving up or down by one step each time someone arrives or departs. Any such random walk must eventually reach the zero point. Thus the unavoidable outcome, if the model runs indefinitely, is that every town but one will shrink to nothing, and the entire population will be crammed into the one surviving Omniopolis.

In a 1965 paper Fuguitt analyzed another probability process, which is quite different in detail but has a similar end point. Instead of directly simulating movements of people, he took as a fundamental event a town's transition from one size class to another. Using probabilities derived from Census data (and allowing for natural increase as well as migration), he found that eventually all towns would grow until they entered the largest class.

The runaway behavior of these models could be avoided in various ways—by a mechanism for creating new towns to replace those that dwindle away, by introducing subpopulations with different preferences in residence, or perhaps by building in an economic incentive favoring less-crowded areas. But such embellishments also bring more adjustable parameters, and the models no longer look so simple.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Computing Science**: Clarity in Climate Modeling

**Feature Article**: Candy Crush's Puzzling Mathematics

**Spotlight**: Briefings