8 ms·

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 st

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-closed-finite-classes-are-recurrent 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)#Proofs_via_the_method_of_stars_and_bars https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)...

Grue3 9y 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.
- jordigh 9y 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.
  - subroutine 9y ago
    I wonder what their point is though? Like, are we supposed to be surprised with the shape of the distribution? Also, while I agree this is theoretically possible to "see everyone hit the maximum amount of money possible for one individual"... given enough individuals the possibility of someone ending up with nearly all the money is close to zero. I've run a simulation with 500 individuals (here: https://github.com/subroutines/DollaBillz https://github.com/subroutines/DollaBillz ) and it seems like the distribution of money reaches a steady-state. What should we make of that?
    - klipt 9y ago
      Think of it as "entropy mostly increases". It's theoretically possible that a bowl of soup left to itself could become hot in one corner and cold everywhere else, but it's vanishingly improbable compared to a mostly uniform temperature distribution.
      - mulmen 9y ago
        I don't understand this example. Are you claiming the laws of thermodynamics only work with a very high probability?
        danharaj 9y ago
        The second law of thermodynamics is intrinsically a statistical law.
        mulmen 9y ago
        I'm not a physicist and I probably could have phrased that a little better. The example of a bowl of soup randomly and unevenly changing temperature implies to me that the physical system behaves randomly which I do not believe it does.
        klipt 9y ago
- un1crom 9y 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/qqplotsgeostart10000.gif 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.
  - ikeboy 9y ago
    Initial condition can be regained, each side moves a horse then moves it back.
    - MereInterest 9y ago
      While that moves the pieces back to their original position, it does not reset to the original game state. After moving the knights back, it would only require 48 additional moves without a pawn moving before the game ends in stalemate, where it required 50 moves at the start of the game.
      - albedoa 9y ago
        Can you expand on this? Where do those two moves go?
        JadeNB 9y ago
        > Where do those two moves go? It's just built into the rules: 50 moves without a capture results in a stalemate (https://en.wikipedia.org/wiki/Fifty-move_rule https://en.wikipedia.org/wiki/Fifty-move_rule). I guess you could say that the two moves 'go' into the implicit state counter that keeps track of the number of moves without capture.
        jumhyn 9y ago
        https://en.wikipedia.org/wiki/Fifty-move_rule https://en.wikipedia.org/wiki/Fifty-move_rule Because both players have already taken two turns, a player can claim a draw after only 48 moves. If the movement of the knights was repeated 25 times, for instance, then either player could claim a draw. However, this is not possible at the beginning of the game, so simply moving the knights back does not actually restore the game state.
- Jabbles 9y ago
  Everyone has 1 dollar except for X who has all the rest.
gragas 9y 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.
- jordigh 9y 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. :-)
  - gragas 9y ago
    I agree with your point. :-) Why is my solution incorrect, though? * Oh, I see why my solution is wrong. It's never the case that one person has all the money. I should take some of my own advice.
- jensv 9y ago
  Counting is just very difficult. You can easily be off by orders of magnitude and not even recognize it.
- Retric 9y 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 9y 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...
- Applejinx 9y ago
  We don't have to. That is 'Western Civilization' :)
gus_massa 9y 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 See also: https://news.ycombinator.com/item?id=14730315 https://news.ycombinator.com/item?id=14730315
- panarky 9y 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 ...
  - Houshalter 9y ago
    What does the distribution look like if you remove the boundary? I think it should be roughly the same.
un1crom 9y 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 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/qqplotsgeostart10000.gif https://github.com/un1crom/givemoneyaway/blob/master/qqplots... enjoy!
logicallee 9y 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 http://i.imgur.com/SctNJWi.png vs with the >$0 redistribution condition: http://i.imgur.com/wRVZxlO.png 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 9y 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.
beagle3 9y 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_theorem https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theor... [1] for a suitable definition of easily. [2] https://en.wikipedia.org/wiki/PageRank https://en.wikipedia.org/wiki/PageRank
deleted 9y ago
[deleted]
andrepd 9y 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 9y 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.

Grue3 9y 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.

jordigh 9y 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.
- subroutine 9y ago
  I wonder what their point is though? Like, are we supposed to be surprised with the shape of the distribution? Also, while I agree this is theoretically possible to "see everyone hit the maximum amount of money possible for one individual"... given enough individuals the possibility of someone ending up with nearly all the money is close to zero. I've run a simulation with 500 individuals (here: https://github.com/subroutines/DollaBillz https://github.com/subroutines/DollaBillz ) and it seems like the distribution of money reaches a steady-state. What should we make of that?
  - klipt 9y ago
    Think of it as "entropy mostly increases". It's theoretically possible that a bowl of soup left to itself could become hot in one corner and cold everywhere else, but it's vanishingly improbable compared to a mostly uniform temperature distribution.
    - mulmen 9y ago
      I don't understand this example. Are you claiming the laws of thermodynamics only work with a very high probability?
      - danharaj 9y ago
        The second law of thermodynamics is intrinsically a statistical law.
        mulmen 9y ago
        I'm not a physicist and I probably could have phrased that a little better. The example of a bowl of soup randomly and unevenly changing temperature implies to me that the physical system behaves randomly which I do not believe it does.
        klipt 9y ago
un1crom 9y 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/qqplotsgeostart10000.gif 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.
- ikeboy 9y ago
  Initial condition can be regained, each side moves a horse then moves it back.
  - MereInterest 9y ago
    While that moves the pieces back to their original position, it does not reset to the original game state. After moving the knights back, it would only require 48 additional moves without a pawn moving before the game ends in stalemate, where it required 50 moves at the start of the game.
    - albedoa 9y ago
      Can you expand on this? Where do those two moves go?
      - JadeNB 9y ago
        > Where do those two moves go? It's just built into the rules: 50 moves without a capture results in a stalemate (https://en.wikipedia.org/wiki/Fifty-move_rule https://en.wikipedia.org/wiki/Fifty-move_rule). I guess you could say that the two moves 'go' into the implicit state counter that keeps track of the number of moves without capture.
      - jumhyn 9y ago
        https://en.wikipedia.org/wiki/Fifty-move_rule https://en.wikipedia.org/wiki/Fifty-move_rule Because both players have already taken two turns, a player can claim a draw after only 48 moves. If the movement of the knights was repeated 25 times, for instance, then either player could claim a draw. However, this is not possible at the beginning of the game, so simply moving the knights back does not actually restore the game state.
Jabbles 9y ago
Everyone has 1 dollar except for X who has all the rest.

gragas 9y 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.

jordigh 9y 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. :-)
- gragas 9y ago
  I agree with your point. :-) Why is my solution incorrect, though? * Oh, I see why my solution is wrong. It's never the case that one person has all the money. I should take some of my own advice.
jensv 9y ago
Counting is just very difficult. You can easily be off by orders of magnitude and not even recognize it.
Retric 9y 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 9y 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...

Applejinx 9y ago
We don't have to. That is 'Western Civilization' :)

gus_massa 9y 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 See also: https://news.ycombinator.com/item?id=14730315 https://news.ycombinator.com/item?id=14730315

panarky 9y 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 ...
- Houshalter 9y ago
  What does the distribution look like if you remove the boundary? I think it should be roughly the same.

un1crom 9y 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 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/qqplotsgeostart10000.gif https://github.com/un1crom/givemoneyaway/blob/master/qqplots... enjoy!

logicallee 9y 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 http://i.imgur.com/SctNJWi.png vs with the >$0 redistribution condition: http://i.imgur.com/wRVZxlO.png 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 9y 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.

beagle3 9y 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_theorem https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theor... [1] for a suitable definition of easily. [2] https://en.wikipedia.org/wiki/PageRank https://en.wikipedia.org/wiki/PageRank

deleted 9y ago

[deleted]

andrepd 9y 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 9y 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.