Why does fair random process lead to unfair result?

Question

Suppose there are 100 people, each one has \$100. Now repeatedly do following:

1. Random choose two people A and B (random means uniform and independent);
2. If A has money, A gives \$1 to B; If A has no money, do nothing;

After doing many times, what is the distribution of money among these people? I guess it should be something like uniform distributed, but it is not. Could you tell me why? Why do some people get so much money from others in this fair process?

Here is the simulation:

n = 100;
a = Table[100, {i, 1, n}];
f[a_] := With[{i = RandomInteger[{1, n}], j = RandomInteger[{1, n}]},
              If[a[[i]] > 0 && i != j, 
              ReplacePart[a, {i -> a[[i]] - 1, j -> a[[j]] + 1}], a]
         ];
b1 = Nest[f, a, 100];
b2 = Nest[f, b1, 1000];
b3 = Nest[f, b2, 10000];
b4 = Nest[f, b3, 100000];
b1 = Sort[b1];
b2 = Sort[b2];
b3 = Sort[b3];
b4 = Sort[b4];
ListPlot[{b1, b2, b3, b4}, PlotRange -> All]

====

UPDATED #1

Consider 3-player case, it can be described by 2d random walk on a triangular lattice. By counting the number of arrivals on each lattice point in $10^6$ walks, we can split points into two groups:

All blue points have almost same arrivals. From this point of view, this problem seems trivial... We can label each blue point with lattice distance from the center, and the "unfair" result can be achieved by points with most common lattice distance.

Answer 1

Another way to see that the "everyone has about the same money" is unlikely is to realize that this simulates a random walk on an $(n-1)$-simplex, taking unit steps along two axes at once. For instance, for two people, this is a random walk along the line a[[1]] + a[[2]] = 200; for three people, this is a random walk along the triangle a[[1]] + a[[2]] + a[[3]] = 300.

The three person case is instructive. The space of possibilities is a triangle, which we can divide into congruent sixths -- place a vertex at the point $(100,100,100)$, the initial condition. Add an edge between that vertex and each of the triangle vertices, at $(300,0,0)$, $(0,300,0)$, and $(0,0,300)$, and an edge between that vertex and the midpoints of the edges, at $(150,150,0)$, $(150,0,150)$, and $(0,150,150)$. These six triangles are congruent and correspond to the six ways that the we could order the three players of our game (i.e., who has the greatest, middle, and least money). Since we are sorting them, this order does not matter, so we may consider just one triangle and draws conclusions from that one.

One triangle has edges $(100,100,100)$, $(150,150,0)$ and $(300,0,0)$. The "fairness" of your intuition can be measured by how far from the vertex $(100,100,100)$ we are. Initially, we start at this vertex and start walking around the big triangle. This corresponds to walking around our little triangle and reflecting off the two edges we added when we cross from one copy of the triangle to another. We still get stuck on the edge that was part of the edge of the original triangle since we still do not allow the person with $0$ money to go into debt.

It takes 200 steps to go from the initial point to the vertex at $(300,0,0)$ and if we had an unconstrained walk, we would expect a few (typically $6$ or $10$, depending on how close to equilibrium counts as "close enough") times $200^2 = 40\,000$ steps to have a 50% chance of displacing as far as the one-person-wins vertex. Since there are some "no transactions" when we hit an edge (extremely likely in the neighborhood of this vertex) it will take many more steps before we can be said to have settled into our long-term behaviour.

However, we can look at the maximum likelyhood outcome. The triangle is symmetric around the line a[[1]]+a[[2]] = 150, so ignoring the "sticky edges" we would expect to be equally likely to be in a situation where one player has more than half of the money or all three players have less than half the money. Note that the sticky boundary is on the side of that line where one player has more than half the money, so if we don't ignore the "sticky line", we expect that (quite a few) more than 50% of random walks (of sufficient length) will produce a player with more than half the money, with the rest split (probably unequally) between the other two (in fact, the median split is $2:1$, with the sticky edge favoring a more extreme split). So, even in the three person game, we expect a very uneven distribution after (say) a quarter million steps.

The analysis with larger $n$ is similar, but more tiresome. Note that the situation is recursive -- ignoring the wealthiest player, the distribution of remaining wealth should be that of the $n-1$ variation of this process, working with total wealth being whatever was left by the wealthiest person. I have not worked through the details, but I recall that this characterises a Pareto process, so I would expect that to be the limiting distribution.

Answer 2

It is often useful to consider the sample space. By doing this, it is obvious that it is more likely for individuals to end up rich than for everyone to stay the same.

Consider the scenario with 2 people having one dollar each represented by (1,1). You will, notice that every (2,0) outcome is equally likely to result in a (2,0) or (1,1) afterwards and similarly with (0,2). Also, each (1,1) is equally like to result in a (2,0) or (0,2). Therefore, at each step, more and more samples are uneven. If we write out the space for a few trials this is clear:

After 1 trial: $$(1,1) \rightarrow (2,0), (0,2) $$

Now, after 2: $$(2,0) \rightarrow (2,0), (1,1)$$ $$(0,2) \rightarrow (0,2), (1,1)$$

Now, after 3: $$(0,2) \rightarrow (0,2), (1,1)$$ $$(2,0) \rightarrow (2,0), (1,1)$$ $$(1,1) \rightarrow (0,2), (2,0)$$ $$(1,1) \rightarrow (2,0), (0,2)$$