When random people give money to random other people (2017)

Summary

A post on Decision Science about a problem of Uri Wilensky‘s has been making the rounds: Imagine a room full of 100 people with 100 dollars each. With every tick of the clock, every person with money gives a dollar to one randomly chosen other person. After some time progresses, how will the money be distributed? People often expect the distribution to be close to uniform. But this isn’t right; the simulations in the post show clearly that inequality of wealth rapidly appears and then persists (though each individual person bobs up and down from rich to poor.) What’s going on? Why would this utterly fair and random process generate winners and losers? Here’s one way to think about it. The possible states of the system are the sets of nonnegative integers (m_1, .. m_100) summing to 10,000; if you like, the lattice points inside a simplex. (From now on, let’s write N for 100 because who cares if it’s 100?) The process is a random walk on a graph G, whose vertices are these states and where two vertices are connected if you can get from one to the other by taking a dollar from one person and giving it to another. We are asking: when you run the random walk for a long time, where are you on this graph? Well, we know what the stationary distribution for random walk on an undirected graph is; it gives each vertex a probability proportional to its degree. On a regular graph, you get uniform distribution. Our state graph G isn’t regular, but it almost is; most nodes have degree N, where by “most” I mean “about 1-1/e”; since the number of states is and, of these, the ones with degree N are exactly those in which nobody’s out of money; if each person has a dollar, the number of ways to distribute the remaining N^2 – N dollars is and so the proportion of states where someone’s out of money is about . So, apart from those states where somebody’s broke, in the long run every possible state is equally likely; we are just as likely to see $9,901 in one person’s hands and everybody...