Counterintuitive problem: People in a room keep giving dollars to random others

http://www.decisionsciencenews.com/2017/06/19/counterintuitive-problem-everyone-room-keeps-giving-dollars-random-others-youll-never-guess-happens-next/

by aqsalose • 9 years ago

555 240 9 years ago

decisionsciencenews.com

jwfxpr2• 9 years ago

Very interesting. I'd like to see this simulation run with different (pseudo-)RNGs. I wonder if and how the quality of the randomness impacts the outcome.

Can anyone with insight offer comment?

dmurray2• 9 years ago

I wouldn't expect it to make a detectable difference, unless the rng was as low quality as the one featured in Dilbert [0] The simulation has to make 100 decisions every turn, sometimes slightly fewer. A typical way to do this is to get 100 32-bit numbers from the RNG, even though you really need fewer bits of entropy than that. If the RNG had cycles of exactly 100, or a factor of 100, that could cause a feedback loop here. But a typical PRNG, even a simple one, has a period length of billions.

[0] http://dilbert.com/strip/2001-10-25

SonOfLilit2• 9 years ago

I wonder, do you have any specific reason to suspect the quality of "randomness" has anything to do with the result?

jwfxpr2• 9 years ago

Well, yes, and as your sibling commenters contributed useful and insightful replies it indicates the question is interesting enough, at least to them, to be worth contributing thought to.

If you're really just looking for an unsubtle way to point out there is some better term of art that isn't salient enough to me to presently recall, perhaps you might wish instead to helpfully point it out for my benefit and that of other readers.

SonOfLilit2• 9 years ago

I hoped to hear a positive response. At the same time, I was trying to impart a lesson that it took young-engineer-me a lot of time to really grasp, which is that you can trust PRNGs and randomness as engineering building blocks (and reciprocal-2-to-the-power-of-a-lot events are unintuitively rare).

On the first:

PRNGs work because they are not random in ways that are very weakly correlated with things you might want to simulate, but there are cases where you do get correlation, and I'm not really sure what those cases are, and read some technical explanations but nothing intuitive enough to be able to look at a real world scenario like this and intuitively grasp that here is one of those rare situations where an LCG is not enough but a Mersenne Twister is, or harder - a Mersenne Twister is not enough but real random data sampled from some physical system and normalized by XORing to a Mersenne Twister is. If you're one of those people that have this skill, maybe you can explain it to me intuitively.

On the second:

The best example is trusting cryptographic hashes. When I was young I saw systems that use a file's hash as that file's unique identifier, that were built on the completely unflexible assumption that there will never, ever be a collision, because that would completely bork the system. I had a bad feeling whenever I saw this assumption being made, because, I mean, yeah, hashes have many bits, but can't it happen even once, somewhere around the world, that two files would be found that have the same hash? There are still so many more files than hashes...

And the answer is no. It can't. Oncce a decade or so your hash algorithm will be successfully broken and you'll need to replace it with a stronger one, but it probably never happened in the entire history of humanity and never will that two files were created that have the same cryptographic hash by coincidence. It's completely reasonable to make this assumption. Just as it is completely reasonable to use a long number as an authentication token, etc' etc'.

We humans simply don't have a mechanism in our brain for representing "a nonzero chance that might happen but is so small that it is inconceivable that it would ever happen even once in the history of the world". So we see "possible" and feel deep in our bones "might happen". And we're worse engineers for it.

lmkg• 9 years ago

I doubt the PRNG will have an effect, unless it's a bad one. For any individual, the flow out is fixed at 1 dollar per round, but the flow in is unbounded. This favors wealth accumulation. If five people happen to select the same donor target, that person will take five rounds to get rid of that money, during which time they are likely to receive more.

Meanwhile if someone only has one dollar, they lose their entire wealth if no one targets them immediately. Only large amounts have staying power.

There is a second-order effect that as money becomes more concentrated there are less donations per round. If one person has five dollars, four dollars are not being donated. This makes being targeted for multiple donations less likely as time goes on.

Retric3• 9 years ago

If you run this for very long time frames everyone should end up both broke and wealthy. It's basically just several bounded random walks which will diverge in both directions and then flip around.

And really this is just another case where random does not seem random to us.

skybrian2• 9 years ago

It favors wealth accumulation, but the winner isn't locked in because eventually any person will lose all they have if they don't get any income for a long stretch.

dmurray2• 9 years ago

If you have $1, you have to give it away, but you receive less than $1 back on average (because some people have no money to give you). So the poor get poorer. But wait, by the same argument the rich get poorer and this simulates a system of stochastic handouts to the very poorest - those with $0.

Alternatively, it simulates a lottery. From the point of view of any individual, every turn you spend $1 on a lottery ticket and get a prize of between 0 and $99. Viewed that way, it's not surprising that some people end up rich in the simulation.

IshKebab2• 9 years ago

The poor have an advantage under this system - they always have an equal change of receiving money but sometimes they don't have to pay any.

rtpg2• 9 years ago

Considering that in order to get this advantage you have to at one point end up with $0, it seems like a bit of a phyrric victory

leddt• 9 years ago

Ah, the lottery analogy does make it more obvious to me. Thanks!

pavlov• 9 years ago

The outcome looks suspiciously like the real-world wealth distributions that we presume to be the result of efficient free markets.

Is capitalism mostly noise?

Retric3• 9 years ago

No, this is fairly linear distribution. Capitalism produces exponential wealth curves.

Further, if you do running average over very long time frames the averages will converge. Aka weathly will become poor then wealthy again.

lou13063• 9 years ago

Except that, in the real-world, wealthy people will spend more money than the poor. I wonder what we outcume would be if each agent spends a random amount of money that depends on their current wealth (say, anything between $1 and 5% of the total).

js82• 9 years ago

Also wealthy people have much bigger gains from investment (what money they already have), which will ultimately cause the distribution to be much more exponential than the one from the simulation.

I suspect giving away a proportion would have no significant effect on the result, because poor and wealthy have still the same likelihood of receiving money.

neilwilson• 9 years ago

Another illusion. A millionaire always spends less than a million people with a dollar.

IshKebab2• 9 years ago

Without the 0 cut-off it's just the binomial distribution.

MrQuincle• 9 years ago

No, you can receive more than you give away as well. So it's not binomial in two ways. :-)

It's really cool though to have a skewed distribution at each time step and a uniform distribution over the entire time series.

It's not exactly the same as just being ergodic. The probability that the distribution is uniform at a particular time step is very small.

dbatten• 9 years ago

I fundamentally disagree that the resulting distribution isn't more or less equal. It's basically randomly distributed around 45, with a pretty small standard deviation to boot...

Drdrdrq• 9 years ago

I think it is Gaussian, not equal. Intuitively, it seems very unlikely that all persons would have the same amount of money at some random time.

jldugger3• 9 years ago

Of course it's randomly distributed around 45 -- conservation of money at work there.

As for the std deviation, the normal rule of thumb is "95 percent of samples fall within 2 std deviations". So basically, all but the highest and lowest. Well maybe two highest, because of the 0 dollar lower bound. A standard deviation of half your starting pool seems pretty high, even if we all have equal chances of being at the far end of the spectrum of results.

detaro• 9 years ago

Worth reading the comments under the post – e.g. people testing it and seeing that values for individual people go from 0 to very high and back over time, which you can't see in the histogram.

aqsalose• 9 years ago

Thanks for pointing this out. It's still fascinating to see how after running the simulation for some time, the ranked histogram appears to be geometric (? [1]) at any given time point, while the wealth of each individual players will go up and down over time.

[1] Didn't check the math.

Dove• 9 years ago

Happens in real life, too. The income level of the top 10% and the top 1% and the top 0.1% are relatively stable in aggregate, but who is in each of those categories changes drastically over time.

lozenge• 9 years ago

Who is in the top 1% changes drastically over time, but it is still mostly people who were born in the top 40% or so. For example, see this chart - https://www.economist.com/news/united-states/21595437-americ...

Or for example -

Studies by the Urban Institute and the US Treasury have both found that about half of the families who start in either the top or the bottom quintile of the income distribution are still there after a decade, and that only 3 to 6 percent rise from bottom to top or fall from top to bottom. - https://en.wikipedia.org/wiki/Socio-economic_mobility_in_the...

Now, you could look at how people/families move around the distribution over longer timescales (multiple generations) but we don't really have the data yet.

nabla9• 9 years ago

For each person its' random walk.

Dollars received is additive process of 99 independent random variables from [0,1].

Dollars given is -1 or 0 if there is none.

The process has memory because givers can run out of money.

arnioxux• 9 years ago

I think this is the correct way to model it. In particular you can model it as a markov chain (commonly studied in queueing theory):

https://en.wikipedia.org/wiki/Birth%E2%80%93death_process#/m...

hawkice• 9 years ago

Less than 99, because some have no dollars, but yes.

dracodoc• 9 years ago

The policy is not symmetric:

1. everybody need to give 1, but may receive 0 (99/100 probability) or 1 (1/100 probability)

2. when somebody run out of money, the total give out is no longer 100 (before this, 100 changed hand in every tick), and the probability of receiving money also changed.

So this is history dependent. The simulation need to run many rounds then compare the results of all rounds.

pimlottc• 9 years ago

Afaict it is possible to get a dollar from multiple players during a round.

gus_massa3• 9 years ago

If on quick reflection you thought “more or less equally”, you are not alone. I asked 5 super-smart PhDs this question and they all had the same initial intuition.

Mmm ... What kind of PhD did they ask? Mathematicians have a strong bias for exact solutions, and not too much intuition for this kind of problems. Have they tried asking Physicists?

It's not surprising that the distribution is not even. I expect that the spread increase in time. I guess something like

average + k1 * sqrt(t) * erf((n- middle) * k2)

where t is the number of simulation steps, and k1 and k2 are some magic constants that I'm too lazy to estimate. ("Proof": Everything is a Gaussian.)

I was surprised that at some point the distribution was almost linear. Perhaps k2 is not a constant, and the correct guesss of the estimation is

average + k1 * sqrt(t) * erf((n- middle) * sqrt(t) * k2')

This estimation fails when t is big. (And it's probably incorrect anyway.)

After some time the person with more money apparently starts to increase the amount of money. I'd like to see a longer simulation to see if after some time the first one accumulates most of the money.

caf• 9 years ago

After some time the person with more money apparently starts to increase the amount of money. I'd like to see a longer simulation to see if after some time the first one accumulates most of the money.

They don't - if you track individual players for a long time, every player ends up having periods of both very high and near-zero wealth.

jordigh5• 9 years ago

We mathematicians have as much intuition as anyone else. I think of this as a random walk on a very large but finite state space with positive n-step transition probabilities between all states for all large enough n. It's an aperiodic irreducible Markov chain. So we should have ergodicity. My intuition now tells me that this means every state is positive recurrent, i.e. for each person x should see x hoard all of the money at some step. Given enough time, a very long time, we should see everyone eventually have all of the money and eventually have none of it. The intermediate steps may look very skewed, but we should see all steps happen.

I'm a bit wary about concluding that just because there's positive probability between all states that we should see all states. At least for infinite state spaces, we know this fails (Pólya's theorem on random walks in dimension 3 or higher). But my intuition tells me that the finite state space should mean that all states are positive recurrent.

Edit: Aha, here's the relevant theorem which confirms my intuition: in a finite-state Markov chain, every closed class is recurrent:

https://math.stackexchange.com/questions/543051/markov-chain...

Untangling the jargon, if you have a random process in which you can go from any state to any other state with positive probability after a certain number of steps, and there are only finitely many states, then the probability of getting to any state as the number of steps goes to infinity is 1.

gus_massa3• 9 years ago

I'm a Mathematician too (+ 1/2 Physicist).

In spite all the states have a probability 1 to be reached infinitely many times, the frequency of each kind of state in the chain is not equal. Some states will have a much higher frequency than the others.

In this case, the states where everyone has a number of coins that is between average-2 and average+2 will be extremely infrequent. They will be reached, but you probably have to wait a lot of time to see them.

But there will be some family of cases that appear very frequently after enough time. I'm not sure if the most common case is

1) Some of the persons has 99% of the money and the rest have a tiny amount of money

2) A few persons have almost all the money.

3) There is some kind of heavy tail distribution were everyone is expected to have some money. If you order them by money you will see something like a wiggly line.

I vote for 1), but I'm not sure at all.

This is similar to the typical thermodynamics problems. Imagine that you have 100 boxes in a line, were you can distribute 100000 "atoms" (or coins). In each step the coins can go to neighbor box at random. This is not the same problem, so it has a different solution.

But it's also ergodic and you can see all kind of weird distribution of the coins/atoms if toy wait enough time.

If you wait enough time you can see for example that all the coins/atom went to the leftmost box and all the other are empty. But this is not common at all.

Most of the time all the boxes will have a number of coins/atoms that is close to the average. (Not exactly the average obviously.)

But this is a different problem with the same state space (100 boxes/persons, 10000 atoms/coins). The rules in the Markov chain are different, so the expected frequency of the states is different.

In the thermodynamic problem, the most frequent states are when the atoms are almost evenly distributed. In the problem of the article, I suspect that the most frequent state is when someone has almost all the money.

js82• 9 years ago

A similar simulation from Peter Norvig (was also on HN): http://nbviewer.jupyter.org/url/norvig.com/ipython/Economics...

colanderman• 9 years ago

Of course it's not uniform. The number of dollars handed to any given person each tick is a random variable drawn from some distribution (too tired to think of which right now). An individual's final worth will probably be selected from some sort of Gaussian, due to the trials being repeated and summed.

Question is, why did they have to hide the solution in a video? Are we allergic to static images and written text now?

bmelton• 9 years ago

I'm usually opposed to video evidence, but in this case, I think the video was an especially good means of illustrating the aggregation of resources to the right in a way that a series of static images would not have captured.

A d3 animation might have done the job just as effectively, but depending on the author's skills, might have taken a very long time to create, comparatively.

execoverride2• 9 years ago

It is not a Gaussian, it is a geometric (i.e. exponential) distribution, since it is the maximum entropy distribution with a fixed mean:

https://en.wikipedia.org/wiki/Maximum_entropy_probability_di...

curiousgal• 9 years ago

Since people are incapable of making truly random decisions, I reckon the person with the most pleasing physical appearance will receive most of the money.

chki• 9 years ago

You should probably read the article, because there are no actual people involved.

snakeboy• 9 years ago

I think it was a joke and not a failure to read the article. Still not contributing to discussion though.

Piccollo2• 9 years ago

Or to the poor if people are feeling charitable

AnthonyMouse7• 9 years ago

This is not surprising. Random doesn't mean homogeneous. Notice that in this model there are rich people and poor people, but advance many iterations and the rich people aren't the same people as they were.

If you want to see the real problem, don't let the people with no money get away with not paying the dollar. Make them borrow it with interest from someone with money.

summer_steven• 9 years ago

Actually, without interest people would have no incentive to lend to others. Any loan carries a risk of not getting your money back. If interest was illegal then the rational move would be to never loan out any money.

schoen2• 9 years ago

Or lending might be done as charity

https://www.hflasf.org/

https://www.jfla.org/

or only upon collateral.

AnthonyMouse7• 9 years ago

If interest was illegal then the rational move would be to never loan out any money.

People would still lend money to their friends and family. Stores would extend credit to customers because they want to make sales.

But regardless, how was that supposed to dispute any part of the post you responded to?

21• 9 years ago

How is then rational for bars to have a "customer tab", with 0 interest typically?

How about clients paying suppliers many months after stuff was delivered?

It is very rational to lend money with zero risk if that gets you more business.

coldtea6• 9 years ago

There are loans without interest. An extra cost/profit is calculated up front (that's e.g. how Murabaha works in islamic banking which prohibits interest). The law still enforces the person to pay back the original amount (or face the repercussions).

(Plus people lend money and tools and whatever all the time with neither interest nor legal guarantees).

ww520• 9 years ago

In a deflationary environment, you can lend out with 0 interest or even negative interest as long as it is smaller than the deflationary rate.

kobeya• 9 years ago

Then apply negative interest to holding money.

shamas• 9 years ago

This would certainly be interesting. One could even keep loading this up with different tax system. Also money could be injected into the system both at a small random rate externally and rarely as an innovation boom following a substantial loan.

wu-ikkyu• 9 years ago

Assuming the number of $ initialized remains constant, wouldn't all of the money end up in with a single player leaving all other players in perpetual debt?

Since the money required to pay the interest is never created, this would create a negative sum game, as players would be charging for money (interest) that doesn't exist.

Doxin• 9 years ago

It would, as it does in the real world.

hedora• 9 years ago

This reminds me of "power of two" balls and bins, which is useful for load balancing. Throwing work onto a random machine doesn't work well. Picking two random machines, and throwing the work on to the less loaded machine is asymptotically better.

I think you'd see something very similar with this type of simulation.

vinchuco2• 9 years ago

It makes sense intuitively: one bit of information (i.e. which machine to assign work to) splits the space into two options and you pick the better one at every comparison

SlySherZ• 9 years ago

I've tried this and the distribution stays pretty close to constant. You can check it out, just comment line 13 and uncomment 15-18: https://www.khanacademy.org/computer-programming/yet-another...

Kenji• 9 years ago

You’ll never guess what happens next.

One of the most annoying and overused phrases in the universe.

jancsika• 9 years ago

This restatement of the problem might help:

"Imagine a room full of 100 people with 100 dollars each. With every tick of the clock, the set of people with money each give a dollar to one randomly chosen other person. The set of people with zero dollars simply lose the opportunity to give away a dollar and thus decrease the overall chances that any participant will receive a dollar. After some time progresses, how will the money be distributed?"

To me this now seems intuitively obvious. Since the game creator has declared by fiat that the number "0" gets a special branch in the program, it stands to reason that the resulting distribution will change once any participant hits zero and triggers that code-path.

For example-- suppose you start with game with one person who has $10,000 and the remaining 99 people have zero. (I don't think you can arrive at that state game organically, but it doesn't matter for the point I'm making.) The first tick through the game all that happens is that the ten-thousandaire gives one dollar to one marginally lucky participant while the other 99 do-- nothing at all. Essentially the 99 all begin by losing a turn.

E.g., imagine an implementation where each tick loops through the participants and the ten-thousandaire happens to be the first participant. If you are the last in line, the only opportunity you have to collect a dollar is when the ten-thousandaire gives away a dollar on the very first iteration of the loop. For the rest of the 99 iterations of the loop you have exactly 0% chance of receiving a dollar. That means on the first tick you and all the other zero-aires would have 1 in 99 chance of receiving a dollar. If on the other hand you started out with everyone having a dollar you would have [some immensely larger chance of receiving a dollar that someone who isn't lazy like me can probably calculate here].

But it's actually worse on the first tick of this example for the ten-thousandaire. That player has a 100% chance of losing a dollar and a 0% chance of gaining one.

I believe this "problem" essentially describes the conditions of an economic depression. It's also a bit of a visual/conceptual illusion because we're likely to look at that chart and see accumulation of dollars as "winning" and zeros as "losing". But if you instead measure liquidity it should be clear that those who accumulated dollars suffer decreased liquidity even worse than the zero-aires.

Also if you remove the special case for zero then the intuition about "more or less equal" distribution should be true.

Edit: change "lose a turn" to "lose the opportunity to give away a dollar" to guard against pedantry. Also, changed "tick/turn" to "tick".

rayiner• 9 years ago

How does the distribution look? Play the movie above to see.

How about I don't play the movie, and you use these magic things called "words" that let you describe experimental results. Maybe we can call these descriptions "abstracts" and put them at the beginning of articles.

albertgoeswoof• 9 years ago

Yea you tell 'em cowboy! Yeeeeee haw!!!

PhasmaFelis3• 9 years ago

Graphs are usually much better at concisely describing numerical data, actually.

jordigh5• 9 years ago

This is an irreducible Markov chain (i.e. it's possible to go from any state to any other with positive probability in a certain number of steps) on a finite state space (because money never enters or leaves the system). This means that every state is recurrent, i.e. will happen if you wait long enough.

This is the relevant theorem:

https://math.stackexchange.com/questions/543051/markov-chain...

This means you should eventually see each person hoard all of the money in turn. Try it with 5 people and 5 dollars each. Then the system only has 29 choose 25 = 23751 states[1], which should give your computer enough time to hit them all.

Edit: Here, Python "proof"

    from random import randint

    numpeople = 5
    initmoney = 5

    ledger = [initmoney]*numpeople

    while True:

        recipients = []
        for i in range(numpeople):
            if ledger[i] == 0:
                recipient = None
            else:
                recipient = randint(0, numpeople-2)
                if recipient >= i:
                    recipient += 1
            recipients.append(recipient)

        for i, recipient in enumerate(recipients):
            if recipient is not None:
                ledger[i] -= 1
                ledger[recipient] += 1

        if max(ledger) == initmoney*numpeople - 1:
            print ledger

----

[1] https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)...

Grue3• 9 years ago

But there's no previous state that can result in one person (I'll name them X) having all the money and everyone else having no money. There are 2 cases:

1) X had some money on the previous turn, giving a dollar to Y. Then Y has at least 1 dollar.

2) X had no money on the previous turn. Then by pigeonhole principle there exists a person Y who has at least 2 dollars. Then Y has at least 1 dollar on the current turn.

jordigh5• 9 years ago

Oops, right. I'm counting the number of states wrong. But the general point stands, you'll see everyone hit the maximum amount of money possible for one individual.

un1crom2• 9 years ago

you can make the first state such that 1 person starts with all the money.

here's how that looks in a 100 person with 100 bucks game (10,000 money supply)

https://github.com/un1crom/givemoneyaway/blob/master/qqplots...

but no you cannot get back to that initial condition.

but in the real world you most definitely can start that way.

chess is like that too... the initial condition can never be regained.

Jabbles• 9 years ago

Everyone has 1 dollar except for X who has all the rest.

gragas2• 9 years ago

The system only has 25^5 states

Not true. The problem is in one-to-one correspondence with the non-negative solutions to

a + b + c + d + e = 25

which is in one-to-one correspondence with the positive solutions to

a + b + c + d + e = 30

which is a simple counting problem---(29 choose 4) = 23751.

In my opinion, you should really try to prove your math to yourself before answering with such an authoritative tone.

jordigh5• 9 years ago

I guess what sounds authoritative is that I'm using jargon while trying to explain the jargon at the same time, as if I knew what I was talking about. I've since edited my comment. I know it's stars and bars, but I keep messing up the count. Anyway, it's a finite amount, it's not huge, and your count is wrong too by a sister comment. :-)

jensv• 9 years ago

Counting is just very difficult. You can easily be off by orders of magnitude and not even recognize it.

Retric3• 9 years ago

One player can't get all the money as they have to hand out a dollar every turn and they can't receive all the money on the same turn.

23751 - 5 = 23746

dv_dt• 9 years ago

Now change the model to introduce even a small bias so that larger collections of money can shift the probabilities of routing that money to them...

Applejinx3• 9 years ago

We don't have to. That is 'Western Civilization' :)

gus_massa3• 9 years ago

I agree with most of your comment, but this part is misleading:

This means that every state is recurrent, i.e. will happen if you wait long enough.

It doesn't mean that the expected frequency of every state in the chain is equal. Moreover, the frequencies are very different.

The interesting part of the experiment is not that each state is reachable. The state where someone has all the money - 1 is reachable. The state where all have the same amount of money again is reachable. But if you leave these people alone in a room for some time and open the door unexpectedly, you will almost sure find out that they have very different amount of money.

I ran an numerical experiment and I get that the average distribution of money is for 5 persons with 5 coins each is:

11.04 6.38 4.03 2.44 1.11

i.e. if you enter the room at random, the one with more money will have on average 11.04 coins, not almost 24 coins

If you count the number of times they have

11±1 6±1 4±1 3±1 1±1

coins, you get a 21% frequency.

If you count the times someone has 24 coins, you get only a 0.00125% frequency. If you count how many times someone has at least 90% of the coins you get 0.0131% frequency (10x more).

This is difficult to compare, because each classification has a different amount of states, but nevertheless, it's clear that an almost linear distribution is more common than a very concentrated distribution.

For 10 persons with 10 coins I get that the average is

28.77 19.11 14.25 10.98 8.53 6.57 4.93 3.53 2.27 1.06

panarky• 9 years ago

From the article's addendum:

The point is not that some people become rich and never lose their top position. This runs infinitely and will contain every possible sequence of good and bad luck for every person.
The richest will become the poorest, everyone will experience every rank, and so on.
The interesting thing is that this simple simulation arrives at a stationary distribution with a skewed, exponential shape. This is due to the boundary at zero wealth ...

beagle32• 9 years ago

I agree with most of your comment, but this part is misleading:
> This means that every state is recurrent, i.e. will happen if you wait long enough.
It doesn't mean that the expected frequency of every state in the chain is equal. Moreover, the frequencies are very different.

I do not find it misleading; I do not see how you equate "if you wait long enough it will happen" with "every state is equally likely" or "the average waiting time to get to any state is the same" (which may or may not be equal depending on your where you consider your starting point).

un1crom2• 9 years ago

the fun is in actually starting from every initial condition and then evolving the simulation out for as many rounds as your computational resources allow....

then do some statistical analysis to categorize the various initial conditions and their distributions.

then inject perturbations in the simulation like "death taxes" and other redistribution policies.

I built up a lot of mathematica code for anyone to play with.

https://github.com/un1crom/givemoneyaway

one of my favs was to start 1 person with all the money and see how long it takes for them to no longer be the richest person in the game.... you know like millions of ticks of the clock.

https://github.com/un1crom/givemoneyaway/blob/master/qqplots...

enjoy!

logicallee• 9 years ago

The article says at the very end:

This is due to the boundary at zero wealth which, we imagine, people don’t consider when they think about the problem quickly.

So I wanted to see if this is true. (I ran 5000 ticks, 45 people, 45 initial dollars each). I used my own program.

I removed the condition that you must have at least $1 to redistribute it (in other words I allowed negative wealth) and ended up with this distribution:

http://i.imgur.com/SctNJWi.png

vs with the >$0 redistribution condition:

http://i.imgur.com/wRVZxlO.png

While it affects the shape, it is far from the case that it looks like some brownian motion near the starting wealth. When sorted, it still has a basically unequally distributed shape.

jdmichal• 9 years ago

There's two asymmetries going on. The first is the one you played with, which is zero hard boundary. But there's also the asymmetry of losing zero to one dollars every round, while gaining zero to n-1 dollars every round. I bet you can minimize the skew by applying a progressive rate to how much is given away, such that you can also lose zero to n-1 dollars every round.

beagle32• 9 years ago

I do not have the time to do this right now, but - as this is a recurrent, finite, state machine, there is a unique stable distribution on states by application of the Perron Frobenius theorem[0] to the state transition probability matrix; that stable distribution on states is a strictly positive eigenvector with sum 1 and eigenvalue 1 (and can thus easily[1] be computed from the sparse 23751x23751 transition matrix)

This, is, by the way, somewhat similar to how Google's original PageRank[2] worked: Each page has some "worthiness capital", and at each point in time, it randomly gives one "worthiness coin" to one of the outgoing links. Give each page some starting capital (e.g, 1,000,000 coins), run the game for a very long time, and rank pages by the capital they managed to collect. There is a big difference, though - each page is not equivalent to a person in the 5-person game, but to a state in the 23751-state space; also, PageRank had damping factors, sink escapes, and other changes, but the basic idea is the same, and was actually (at least) 20 years old at the time that Page and Brin applied it to links of the "href" kind.

[0] https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theor...

[1] for a suitable definition of easily.

[2] https://en.wikipedia.org/wiki/PageRank

andrepd2• 9 years ago

I don't think this is relevant, though. It really doesn't matter that the process reaches every configuration given enough time; the post is about the limiting behaviour. Take roulette for example. If played long enough it will pass through every configuration with 100% certainty; yet its limit is -∞ dollars.

ruste• 9 years ago

It's not possible for one person to ever have all of the money unless they have the possibility of not giving money away. Imagine the most optimistic state scenario just prior to hopefully having a state where one person has all the money. In this scenario everyone but our lucky rich guy has one dollar and the rich guy has all the rest. On state transition everyone gives the rich guy a dollar, but the rich guy still has to give a dollar to someone.

kazinator• 9 years ago

Intuitively, I would expect that we can collapse the result of doing this type of dollar scrambling over many iterations of the simulation into a single operation which takes a sequence of dollars and partitions it into N randomly-sized partitions for N people.

For instance, we can arrange the dollars into a sequence and then insert N-1 randomly-placed divisions to chop up the sequence. Then each of N people in the corresponding people sequence gets their corresponding (possibly empty) piece of the dollar sequence.

If we distribute randomly placed chops into section of the real number line, we end up with string lengths that follow an exponential distribution: https://en.wikipedia.org/wiki/Exponential_distribution

It is not intuitive at all to expect the pieces to be more or less identically long (which corresponds to the wrong intuition that everyone will have more or less their equal share of the dollars). That would mean that the chops are evenly spaced and not random.

Randomly placing chops is a https://en.wikipedia.org/wiki/Poisson_process

However, part of the intuition here (possibly wrong) is that Poisson is applicable to a crudely discrete process like this, in some approximate way.

unoti• 9 years ago

The lack of money "accumulates" because you always have a chance to receive money, but when you run out of money you cannot give more. So there is a lower cap but no more upper cap.

In the real world this is even worse. Once you're out of money your chances of getting money go down drastically.

Piccollo2• 9 years ago

What would happen if there was an upper cap?

amelius• 9 years ago

Now invent a tax rule that brings back the equality. And simulate it.

And then simulate how this tax rule works in a capitalist market model.

I'm curious.

qubex4• 9 years ago

You're missing a subtle point: not only is the distribution exponential, but also as time progresses various agents exchange their positions in top and bottom categories. So if one introduced a taxation system that redistributed equality to create a uniform distribution, you would also enforce utter social immobility. I doubt that is desirable (basically you'd be recreating the drabbest kind of communist regime known to mankind).

petermcneeley2• 9 years ago

This problem lead to the discovery of Quantum physics. Simply replace the $1 with energy quantums.

https://www.youtube.com/watch?v=SCUnoxJ5pho&feature=youtu.be...

Nydhal• 9 years ago

The difference I see, is that in the OP game every player is guaranteed to give out $1 at each step, while in the video, a player is chosen at random to give out $1. I don't know how this might change the long-term distribution.

petermcneeley2• 9 years ago

Insightful point, especially considering what the difference might mean on the physics side. Aka a time evolved system of uniformly every particle that has energy donating some energy to another random particle vs random particle donating energy to another random particle.

chrisallick• 9 years ago

I don't see why it's counterintuitive. If we know that "random" distribution will place values on a curve, then why would it not follow that the money would distribute this way and lead to inequality.

But I like the article! Excited to share to students.

subroutine4• 9 years ago

I've coded this sim (ml/octave) if anyone wants to play around with other numbers (number of people, starting amount of dollars):

https://github.com/subroutines/DollaBillz/

The writeup there includes a clip simulating 500 people (each starting with 100 dollars) and some distribution fits.

pontus• 9 years ago

As others have noted, every state in the state space will eventually be explored and so the appearance of convergence is a little misleading. Eventually the richest person will lose all the money and someone else will take that place.

An interesting question is why we happen to see the system in such an unequal state when we look at it after e.g. 10000 iterations. The reason for this, I believe, is entropy. There are just vastly more ways to distribute the money unequally than equally (thinking of these as macro states). For example, there is only one (macro) state where everyone has $100, but there are 100! states where the money is distributed in a perfectly unequal way (e.g. 0, 1, 2, ..., 99, 5050 or any other way where all the people can be distinguished). So, if you randomly peek at the system at any given time it'd be very unlikely that you'd see it in any way other than a highly unequal state. To be fair, this argument neglects the dynamics (perhaps the transition probabilities to those states are sufficiently small that the n! multiplicity is watered down, although I suspect this is not the case.)

pishpash2• 9 years ago

In this simulation, the amount of money you have does not affect how much you have to give away per round (until you get to $0, in which case you give away nothing) or how much you will get per round (until some people get to $0, in which case the money you get is less on average). So in most cases, with whatever you have, you are expected to see a gain distribution with zero mean. Since it's not a self correcting process other than at the $0 end, it's not surprising to see (1) a snapshot with uneven distribution, (2) no one dropping out permanently.

Actually I don't know what is the point they are trying to make with this video. There is neither anything surprising in the general sense nor a solid statement about what is specifically seen.

k__• 9 years ago

How would it change if it was 1% instead of $1?

anigbrowl5• 9 years ago

The point is that it's counterintuitive even to intelligent people, and that matters because politics and economics are largely driven by the accumulation of intuitive decisions.

vinchuco2• 9 years ago

eventually

can be a long time

kharms• 9 years ago

I love this! If I had to ELIA5 it, I would say: if you get lucky you get rich quickly. If you get unlucky you get poor slowly. So some people will get lucky and some will get unlucky, but the first to get unlucky will get below 100 and the first to get lucky will get above 100, explaining the initial behavior.

tootie• 9 years ago

Put another way, the key is that for n people and n dollars, you can receive up to n-1 dollars in a given turn, but you can only ever lose 1. Therefore, whoever is lucky early will accumulate faster than they can distribute.

daveFNbuck• 9 years ago

Because expectation is linear and the total amount of money in play never changes, we know that the sum of the expectations for each player over a given turn is equal to 0. If no players have run out of money, this means that the expected change for each player over a single turn is zero.

If instead we have m players with money and b broke players, each player still has an equal expected number of dollars received, and the m players with money each expect to give 1 dollar. Summing this, we have a total expected change of (m + b)E(received) - m, which must equal zero, meaning E(Received) = m/(m + b), so players with money expect a change of -b/(m+b) and players without money expect a change of m/(m+b).

This tells us that the expectation for a turn is basically always zero and never gets above zero in a way that allows accumulation of wealth for a single player. So over long periods of time we should expect this to look like a drunk walk with a weird distribution.

dmayle• 9 years ago

The only reason why anyone might find this surprising or counterintuitive is that they're using a terrible visualization. Dollars should be on the x-axis, and number of people should be on the y-axis. If you had that, you'd see this slowly converge to a standard distribution (bell curve).

nsnick• 9 years ago

We see this result because as a percentage of their total wealth, the poor are giving away a larger portion. Try this experiment again, but instead of having everyone give $1 to a random person, have everyone give 1% to a random person.

Zeebrommer• 9 years ago

Interesting phenomenon! To me it makes intuitive sense when viewed as a uniform distribution of money between 0 and ~$100. Bottom graph approaching linear.

In that light these kinds of posts can be a bit disappointing: "here, have a simulation to prove the phenomenon". Yes but how does this work in general? As others have noted, is it stable over time? Which factors play a role in the speed of convergence? What if one introduces tax per transaction, giving the returns to the poorest? What would be a fair percentage?

usaphp• 9 years ago

gives a dollar to one randomly chosen other person

I wonder is the person randomly chosen by the machine or is it randomly chosen by the person who gives away the dollar? If it's the second case - I wonder how much does personal attraction matters here. Unconsciously you would want to give something to a person who you find more attractive...

wungsten• 9 years ago

I'd like to see you try programming a simulation with that in mind :)

PhasmaFelis3• 9 years ago

If the giver is allowed to choose, it's not random, by definition. You'd need a computer or some other reasonably good randomizer, like dice.

whatnotests• 9 years ago

Wait wait wait wait.

You mean we don't naturally end up with 1% of the people having 99% of the dollars??

Cosmopolitan• 9 years ago

It is not randomly chosen by the person who gives away the dollar. Personal attraction matters here. Unconsciously you would want to give something to a person who you find more attractive.

PhasmaFelis3• 9 years ago

...We're not talking about actual people in an actual room with actual dollars.

ineedasername2• 9 years ago

Hmm, I ran a few trillion cycles of this and got nowhere: the average never changed at all. :)

scottmsul• 9 years ago

This kind of simulation results in an exponential distribution, which is fairly equal compared all things considered. In an exponential distribution, most people have roughly the same order of magnitude of wealth (10s to 100s of dollars). In real life, the bottom 99% follow an exponential distribution pretty closely, while the 1% follow a pareto distribution, which is WAY More unequal. The transition is very sharp too, and has been studied in econophysics models.

Brief introduction to econophysics for the mathematically inclined: https://arxiv.org/abs/0709.3662

xrd• 9 years ago

I don't understand the math here. But, it seems people are saying there is equal probability that any state can arise. Is that correct? If so, I'm unclear why that's true given that the state where one person has all the dollars seems like it can only arise from a much smaller set of states (where only one person, and there would be 99 options, had one dollar and one person had all the rest). In comparison, wouldn't there be lots of times when the next state (say where all the people had similar amounts of money) would be easier to get to from multiple states. I'm saying it simplistically seems like the extreme states are harder to get to than the "middle" states. Is than an erroneous assumption? Is there some technique I can use to reason about this problem in a different way?

abalone• 9 years ago

I'm not saying I'm smarter than your average PhD but it seemed intuitive that it would concentrate wealth, basically because you can only give out 1 dollar per round even if you have >1 dollars.

Having said that I would not draw too much inference about economics and human society from this. There is no such "1 dollar per round" rule in life.

anigbrowl5• 9 years ago

People can be smart about many other things besides quantitative reasoning and get PhDs in those other subjects.

robotresearcher• 9 years ago

It does not stably concentrate wealth. It does create short-term inequality of wealth. Every player will be the richest at some point if you play long enough.

dskloet• 9 years ago

I would have expected them to follow Zipf's law.

https://en.wikipedia.org/wiki/Zipf%27s_law

Vsauce made a video about it: https://www.youtube.com/watch?v=fCn8zs912OE

jonahrd• 9 years ago

Is this a case of Zipf's law? It looks like it to me, can someone confirm?

pluma• 9 years ago

Not quite. It looks pretty exponential but the highest value is not twice the second-highest value (and so on).

jldugger3• 9 years ago

IMO, this reveals more about human intuition regarding randomness than whatever financial point it purports to make. It's still a useful point though.

Reminds me of the load balancing literature. There, the explicit goal is to evenly divide the burden across your fleet of servers, and having wide distributions is a problem on both ends: you're paying for servers to sit idle, and some are over burdened and giving customers a bad experience (high pageload times).

By way of illustration, I took the code and made a simple modification to it, implementing power of 2 random choice (http://www.eecs.harvard.edu/~michaelm/postscripts/tpds2001.p...).

Here's the video result: https://www.youtube.com/watch?v=94Vc7gf3ONY Much tighter distribution, though you need to be able to identify the size of people's bank accounts. In this model, it's very rare for anyone to give the richest anything, unless you magically choose two people randomly tied for richest.

jldugger3• 9 years ago

It converges there pretty quickly. So I put together another video starting out with an imbalanced curve (maybe due to a rolling app deploy) smoothing back out. As you might expect, it gets there rather quickly: https://www.youtube.com/watch?v=wvnwx4r2ERA

execoverride2• 9 years ago

What is happening here is fairly simple: Since each state in the system occurs with the same probability, the distribution that arises is the one that maximizes the entropy. Since the total amount of money is conserved, this means that the mean of the distribution is fixed. The maximum entropy distribution in this case has a geometric shape, which is skewed:

https://en.wikipedia.org/wiki/Maximum_entropy_probability_di...

pishpash2• 9 years ago

Yep, it's just a simple counting argument, you see the distribution that has exponentially more states than any other, subject to constraints. Specifically, you are allowing the range [0,∞). If you had constrained it to a fixed range of money (e.g. there is corrective feedback when you get too much money), then you would have seen a more uniform distribution.

RodgerTheGreat2• 9 years ago

I whipped up an interactive simulation of this effect in K:

http://johnearnest.github.io/ok/ike/ike.html?gist=f974a638c4...

Source, for the curious:

    p: 72                                       / players
    s: p#100                                    / score
    c: {(+/(!#x)=/:(+/t)?#x)-t:0<x}             / change (per round)
    
    b: {[c;p;y;x](p+0,2*y;;x#c)}                / draw bar (color;pos;y;x)
    g: {x'[!#y;_60*y%|/y]}                      / draw graph (bar;data)
    
    tick: {{s+::c s}'!20}                       / iterate several steps/frame
    draw: {g[b[3;10 10];s@<s],g[b[2;90 10];s]}  / graph sorted, raw value

froggerplayer• 9 years ago

I'm the author of the blog post OP points to. I'm impressed and intrigued what you've done here. Want to learn more about K.

RodgerTheGreat2• 9 years ago

As a brief summary, K is what's called a "vector-oriented" language; functional, very concise, naturally parallel. The canonical implementation(s) of K are commercial products sold by Kx Systems, and offer extremely high performance. I personally maintain an open-source clone implemented in JavaScript which is comparatively quite slow but is suitable for tinkering and prototyping.

The above program was implemented in iKe, a browser-based livecoding environment I built on top of my interpreter:

https://github.com/JohnEarnest/ok/tree/gh-pages/ike

The concision and flexibility of K is a huge boon for this kind of interactive development. I wrote my simulation in a few minutes, and most of that time was spent deciding how I wanted to draw my histograms.

If you have any more specific questions I'd be happy to try to answer them.

anigbrowl5• 9 years ago

I don't have R installed and don't want to spend the rest of teh day setting up packages and trying to get animations underway, but I'd like to explore two other scenarios:

a. Same rules (100 people, 100 dollars), but everyone has to give away 1% of their wealth instead of $1 each round.

b. Same rules as the original, but anyone who has $0 at the end of a round 'dies' and is no longer able to participate.

We have simulation games like Simcity, Civilization, the Sims and so on. I wonder why there aren't better economic simulation games. I know of various academic tools but I mean games that would be accessible and enjoyable for consumers while also allowing them to easily explore simulation spaces. You can mess around with tax policy in simCity type games, for example, but it's really primitive. Academic economic simulation tools tend not to be very engaging (since they're not built to entertain) and also have ugly visuals and user interfaces.

plouffy• 9 years ago

Don't need any simulations to tell you what (b) would look like. Over the long run, you would be left with only 2 players since everyone else would eventually die out.

phatoni• 9 years ago

Given the uneven distribution of wealth being more likely then an even distribution of wealth per tick. If you now add the rule that someone having less than $100 is unhappy and someone having at least $100 is happy you end up with lower overall happiness on average compared to the initial state were erveyone has $100 and would be happy with that.

curiousgeorgio• 9 years ago

This model essentially represents an economy wherein every person spends exactly what they make, and in the real world, there are plenty of people who behave that way (at every position on the wealth spectrum).

However, it also ignores the fact that for the most part, people are not forced to live that way. Sure, there's a certain minimum cost associated with simply staying alive, but there's also tremendous potential for people to save and/or invest (a portion of) their money rather than spend it, which in turn may increase their likelihood of being on the receiving end of other people's "random" expenses. It also ignores the fact that for every dollar spent in this economy, we can assume that a dollar of value is received in return. If a person spends a dollar truly randomly (or frivolously), then that expense has an opportunity cost, and in many cases (above a baseline for basic living expenses), that dollar would be better spent/invested in activities that will increase the person's future money-making power.

I suppose if all those points were included in the model, we'd probably see even more inequality in the wealth distribution at the top end, but on the middle-to-low end, there's no reason it couldn't be much flatter; when people fall on hard times (as all will eventually), they can make the difficult-but-necessary decision to spend less than they make, thereby slowing or reversing any downward trend. Philanthropic activity would also help the unlucky few on the extreme lower edge of the distribution to bounce back quickly.

Of course, the real problem in this scenario is that we should never underestimate the number of people who just don't care - or those who spend their money more "randomly" than not, with little concern for the future. Those are the same people who later on will be lining the streets protesting about how "unfair" the system is when they're finally broke.

ivoras• 9 years ago

So I've repeated the experimental model. Yes, if at each step everyone gives $1 to a random person, the same thing happens as in the article: https://www.youtube.com/watch?v=Hu0vcn_-vX4 .

If, instead, at each step, everyone gives 1% of their currently held amount, this happens: https://www.youtube.com/watch?v=N8Ce3eQTA9c .

The results are radically different. Draw your own conclusions.

Falkon1313• 9 years ago

This is a bit too "spherical cow in a vacuum" for my tastes. As a quick experiment, I included population growth (using average population growth rate of the US over the last 50 years) and GDP growth (again using US average for last 50 years). Assumptions being that new population start with $0 and GDP growth applies equally to all as a percentage of their then-current wealth. It substantially enhanced the inequality.

In the simple run, median/mean was 67%, but with compounded growth it was only 7.9%. Moreover, the standard deviation went from 1.31 times the median (87% of the mean) to 17.83 times the median (141% of the mean).

https://gist.github.com/anonymous/4f6c546a776a8ab142235c8617...

Wonder what it would be like taken further - forcing population that have $0 to take a loan from the wealthiest people and pay them interest.

kirillseva4• 9 years ago

without any cap it doesn't look fun for the unlucky person. Take a look at my other comments on this thread, there's a link to a gist that generates an animation with the same starting conditions as OP, but forcing the person with $0 to borrow and introducing an interest rate of 10%. At some point the system destabilizes and the debt of the unlucky person goes out of control.

TIL what an economic crisis is and how it happens

nullc• 9 years ago

I believe happens because the states where everyone has close to the same amount of money have lower entropy e.g. there is only 1 state where everyone has equal money, but there are by far more states where the funds are exponentially distributed.

If it makes you feel better, in this model eventually everyone will spend time as both rich and poor... probably not so much like the real world. :)

lohankin• 9 years ago

Let's consider a different problem. There are 100 non-negative numbers summing up to 10000. Let's choose a random combination of numbers satisfying this condition. Intuitively, it's quite clear that typical case will be very different from equilibrium (where every number=100). I fail to see how the transfer of 1 dollar at a time is qualitatively different. So the result is quite intuitive - contrary to what the article suggests.

recursive• 9 years ago

A random distribution of points in a circle is different from a set of points calculated by using a random angle and distance from the center, even though they're both "random". How you construct your randomness is significant.

raldi• 9 years ago

I don't understand the video -- with 45 players, wouldn't one have $89 after round 1? But that's not what we see -- it takes hundreds of rounds before the first person breaks $80.

Klathmon• 9 years ago

Each person chooses the person they give their dollar to independently.

It's not one chosen person getting all the money from that round.

lngnmn• 9 years ago

"Dollar studies" is perhaps the second bullshitest part of psychology after "infant-looking-times studies".

Artificial cartoon-like setups and biased interpretations cannot be considered scientific or even accurate.

Babies are merely confused and overwhelmed, dollar studies are over-simplified and sterile and does not take complex emotional and hormonal patterns (which are much more powerful than rationality biological driving forces in real life) into account.

Snap-judgements, jumping to conclusions, escaping from emotional pressure and reduction of cognitive load is what derives people's behavior. Any sales or ad professional would confirm this.

hasenj• 9 years ago

I wonder what would happen if every 20 or so rounds, each player is given a new set of dollars (say 5 dollars), to sort of simulate UBI.

kirillseva4• 9 years ago

Modified the problem from this post to also include debt. If someone doesn't have the funds to pay during the turn, they have to borrow money from the person they should be giving it to, and pay back with interest.

Check out the source and the produced animation here: https://gist.github.com/kirillseva/961fa1f5b5d64254e0117caf1...

kirillseva4• 9 years ago

with the following parameters:

  NUM_PEOPLE    = 45
  INITIAL_BANK  = 45   # everyone gets 45 dollars
  INTEREST_RATE = 0.1  # 10% per turn that you didn't pay
  ROUNDS        = 5000
  RENT          = 1    # how much to pay each round

everybody's cash goes to zero on step 1008. From that point on all trades are debt manipulations only

edit(formatting)

e12e2• 9 years ago

everybody's cash goes to zero on step 1008

Surely not in the highly improbable case of everyone starting with 1 dollar, giving money to someone else in a chain that leads back to themselves? Theoretically such a system could continue indefinitely? (a gives to b gives to c gives to.... a)?

adrianmonk• 9 years ago

Lots of complicated explanations why this doesn't strongly tend toward being very even. Here's my attempt to state it simply.

Every round, each person (except those who are broke) definitely gives away $1. They may or may not get a dollar. They might even get more than a dollar.

So it's not surprising that some get a bit ahead and others fall a bit behind.

qubex4• 9 years ago

I guessed an exponential distribution of wealth right after the problem was posed. Apparently years of crying hot tears over agent-based economic simulations served my intuition well.

daddyo• 9 years ago

High school diploma solution:

There are increasingly more ways to distribute wealth unevenly, than evenly.

Reduce the problem to the simplest case of 3 persons: `a`, `b`, and `c`. Person `a` has decision to give to either `b` or `c`. Then use combinatorics:

    from itertools import product

    decisions_a = ['ab', 'ac']
    decisions_b = ['ba', 'bc'] 
    decisions_c = ['ca', 'cb']

    for combination in product(decisions_a, decisions_b, decisions_c):
        print combination

    >>> ('ab', 'ba', 'ca') # uneven
    >>> ('ab', 'ba', 'cb') # uneven
    >>> ('ab', 'bc', 'ca') # even
    >>> ('ab', 'bc', 'cb') # uneven
    >>> ('ac', 'ba', 'ca') # uneven
    >>> ('ac', 'ba', 'cb') # even
    >>> ('ac', 'bc', 'ca') # uneven
    >>> ('ac', 'bc', 'cb') # uneven

100ideas• 9 years ago

More interesting: "wealthier" person gives 1/2 their wealth to "poorer" person every turn.

Probably looks like Boltzman distribution describing velocity of ideal gas.

Counterintuitive problem: People in a room keep giving dollars to random others

Related Stories