Hacker News Reader

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

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

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 ...

What does the distribution look like if you remove the boundary? I think it should be roughly the same.

Removing the boundary doesn't really make sense -- if you allow people to go into negative dollars but still be able to give a dollar each tick, then there's no longer a finite amount of money in the system.

Sure there is, it's just effectively a zero interest debt instrument. Imagine that everyone is exchanging IOUs, instead of physical dollars.

You misunderstand. The parent meant that the amount is infinite, so the property that eventually every state will happen is no longer there.

Wow, a mathematical explanation of how uncapped debt reduces wealth mobility.

You're kidding, right? No way a generic observation about a markov chain (which doesn't even model interest) implies that "uncapped debt reduces wealth mobility".

So, with typical debt, interest rates are higher for debt than for savings. Does seem that a) removing the cap, and b) introducing interest on savings < debt would trap some people in poverty?

IOUs are money, in a model this simple.

It should be fairly anti-symmetric, since the dynamics of losing are similar to those of winning. So instead of exponential looking, it's shaped like exp(rank) - exp(-rank). (just confirmed this with a quick simulation)

With participants able to go into debt indefinitely, the process becomes a random walk.

The result should be each participant being up or down from 0 at a rate of proportionated sqrt of t, the number of iterations of the system. Implying a wealth distribution which would become ever-more skewed over time.

Is that what "skewed" means? To my mind a widening bell curve which remained symmetric (which is what we're talking about, right?) would not be "skewed".

"Varied" or "widely distributed" seem like better terms. To my mind, "skew" is what we have in the original problem (with a zero-bound) - it only describes asymmetric distributions.

Over time, the average participant would have either far more coins in credit than they began with or be in debt for far more coins than they started with.

Whether you have what statistician call "skewed" or not, you have what most people would call skewed, unequal, extreme.

> 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).

As someone who has had to study a lot of probability and modeling in my life (for starters, see: Exam 1/P), I agree completely with you.

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.

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.

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 ) and it seems like the distribution of money reaches a steady-state. What should we make of that?

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.

I don't understand this example. Are you claiming the laws of thermodynamics only work with a very high probability?

The second law of thermodynamics is intrinsically a statistical law.

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.

Entropy can decrease, just with vanishingly small probability: https://en.wikipedia.org/wiki/Fluctuation_theorem

You don't have a detailed knowledge about the state of every molecule in the bowl soup and its environment, so you have to rely on statistical mechanics. And the current macroscopic state that you observe could correspond to a particular microscopical state that evolves in surprising ways. But the probability is so low that it just doesn't happen.

To make things worse, quantum mechanics is intrinsically random (at least as far as we know) and having a detailed knowledge of the state of the system allowing for certain prediction of its evolution is impossible in principle (and not just in practice).

Yes, the second law of thermodynamics is a statistical law. It is physically possible that all the particles in an ideal gas container will be moving east all at the same time, for example (it doesn't break any law of mechanics), or that a temperature fluctuation will spontaneously appear in a material in thermal equilibrium. It's just that the probability for such spontaneous entropy decreases happening is astronomically small.

Ok right. It just seemed like the article and jordigh were making contrasting points. Although neither make an explicit broad claim (in which case, what are we doing here other than running an arbitrary MCMC and then stating a Markov property), the article is saying hey look, rich people get richer, while jordigh is saying, nah "you should eventually see each person hoard all of the money in turn.".

So which is it, probably? I think this might be more complex than "everyone will hord all the money eventually", given that the most probable number of sign changes in a 1D random walk is zero.

I'm disinclined to attribute them with having much of any point at all. Their discussion is too brief, and their presentation style is more clickbait thance science. They tout a counterintuitive result (It's really not, at least not for anyone used to thinking about data or state changes, certainly not once you think about what the 4th or 5th state change looks like) And then it ends the headline with the overused, even in for content farm clickbait, "you'll never guess what happens next". This tells me they're less interested in discussing an interesting result than getting eyeballs on the page via a shallow observation passed off as insight. If there's a deeper point to be made, they haven't made it.

Thank you. Finally someone said it. This was not the least bit counterintuitive to anyone familiar with randomness.

We're they trying to imply that people should assume the distribution would remain uniform?. That strikes me as more "insane" than intuitive.

It's simply a function of how the tokens are being exchanged that would almost require some actors get the short straw, and since this is happening 100 times per round, that randomness ensure some actors get progressively shorter straws over time, because randomness is neither fair, not even. It's randomness.

No, they're making a simple digital model that conclusively disproves the notion that 'because disparity in wealth exists, meritocracy exists'. Knowingly or not, that's the point being made.

If you want an even more insanely staggered distribution, let people with resources increase their chances of being given a dollar. This establishes that even in the complete absence of merit, a striking distribution will arise and stably persist, and it's created out of the mechanical behavior constraint of 'possibly being broke and having no dollar to give'. That alone creates what looks like a 'meritocracy' with 'high performers'.

Add literally any form of actual merit, and this gets more extreme still. The funny thing is, the merit-less distribution is not wildly out of line with what people think the distribution should be WITH merit.

I feel like there's some weird fundamental misunderstanding going on here.

The way I interpreted the solution was that every individual will at some point have the max possible amount of money (which is roughly $100).

I don't think jordigh is trying to imply that a single individual will have a majority of the total wealth

Everyone starts with $100, and there are 100 people, so the max possible would be $100 * 100 - 1

(minus 1 because you give away $1 on every turn).

Assuredly, but this is the same as with a deck of cards. If you apply a shuffle that you know creates a closed markov chain (say, moving the top card to a random position within the deck), then you will reach a steady state. But, given enough shuffling, you'll also return to a new deck order

A dose of realism would have anyone with >$x be able to reduce the amount or frequency of giving away money. Or be able to spend some of their wealth on 'marketing' and increase the likelihood of being the recipient of any particular dollar being given away.

Not to demonize accumulation of wealth but just to model reality where rules can sometimes be changed by those with enough wealth accumulated.

True, but I think Grue3's remark is more about the fact that this Markov chain is not irreducible than the number of states being wrong. Because you can go from the state where one person has all the money to the other states but not the other way around.

This doesn't matter all that much -- I think the Markov chain becomes irreducible if you chop off the states in which one person has all the money.

Why would that not matter? If you ignore some states that are possible is that not changing the problem?

In this case, the unreachable states don't partition the space in a meaningful manner, nor does the system start in an unreachable state, so the only effect is that those states occur with probability zero instead of with very low probability in the stationary distribution. There are also very few (N) of those states compared to the total number of states (about N^(2N) if I'm estimating right), so removing them has very little effect on the overall statistics.

For a more interesting example, suppose that on each round, everyone with money picked a random person and gave them 2 dollars (and take N even). Now you'd have a Markov chain that is reducible in a nontrivial manner -- think about the parity constraints.

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.

Initial condition can be regained, each side moves a horse then moves it back.

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.

Can you expand on this? Where do those two moves go?

> 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). 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.

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.

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

>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.

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. :-)

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.

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

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

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!

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...

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

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.

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.

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.

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.