https://quomodocumque.wordpress.com/2017/06/27/when-random-people-give-money-to-random-other-people/ Quomodocumque Math, Madison, food, the Orioles, books, my kids. * Home * About * Booklist 2011- * How Not To Be Wrong Jun 27 2017 18 Comments By JSE math When random people give money to random other people A post on Decision Science about a problem of Uri Wilensky's has been making the rounds: Imagine a room full of 100 people with 100 dollars each. With every tick of the clock, every person with money gives a dollar to one randomly chosen other person. After some time progresses, how will the money be distributed? People often expect the distribution to be close to uniform. But this isn't right; the simulations in the post show clearly that inequality of wealth rapidly appears and then persists (though each individual person bobs up and down from rich to poor.) What's going on? Why would this utterly fair and random process generate winners and losers? Here's one way to think about it. The possible states of the system are the sets of nonnegative integers (m_1, .. m_100) summing to 10,000; if you like, the lattice points inside a simplex. (From now on, let's write N for 100 because who cares if it's 100?) The process is a random walk on a graph G, whose vertices are these states and where two vertices are connected if you can get from one to the other by taking a dollar from one person and giving it to another. We are asking: when you run the random walk for a long time, where are you on this graph? Well, we know what the stationary distribution for random walk on an undirected graph is; it gives each vertex a probability proportional to its degree. On a regular graph, you get uniform distribution. Our state graph G isn't regular, but it almost is; most nodes have degree N, where by "most" I mean "about 1-1/e"; since the number of states is N^2 + N - 1 \choose N-1 and, of these, the ones with degree N are exactly those in which nobody's out of money; if each person has a dollar, the number of ways to distribute the remaining N^2 - N dollars is N^2 - 1 \choose N-1 and so the proportion of states where someone's out of money is about \frac{(N^2 - 1)^N}{(N^2 + N - 1)^N} \sim (1-1/N)^N \sim 1/e. So, apart from those states where somebody's broke, in the long run every possible state is equally likely; we are just as likely to see $9,901 in one person's hands and everybody else with $1 as we are to see exact equidistribution again. What is a random lattice point in this simplex like? Good question! An argument just like the one above shows that the probability nobody goes below $c is on order e^-c, at least when c is small relative to N; in other words, it's highly likely that somebody's very nearly out of money. If X is the maximal amount of money held by any player, what's the distribution of X? I didn't immediately see how to figure this out. You might consider the continuous version, where you pick a point at random from the real simplex (x_1, .. x_N) \in \mathbf{R}^N: \sum x_i = N^2. Equivalently; break a stick at N-1 randomly chosen points; what is the length of the longest piece? This is a well-studied problem; the mean size of the longest piece is about N log N. So I guess I think maybe that's the expected value of the net worth of the richest player? But it's not obvious to me whether you can safely approximate the finite problem by its continuous limit (which corresponds to the case where we keep the number of players at N but reduce the step size so that each player can give each other a cent, or a picocent, or whatever.) What happens if you give each of the N players just one dollar? Now the uniformity really breaks down, because it's incredibly unlikely that nobody's broke. The probability distribution on the set of (m_1, .. m_N) summing to N assigns each vector a probability proportional to the size of its support (i.e. the number of m_i that are nonzero.) That must be a well-known distribution, right? What does the corresponding distribution on partitions of N look like? Update: Kenny Easwaran points out that this is basically the same computation physicists do when they compute the Boltzmann distribution, which was new to me. Share this: * Click to email a link to a friend (Opens in new window) Email * Click to share on Facebook (Opens in new window) Facebook * Click to share on Reddit (Opens in new window) Reddit * Click to share on X (Opens in new window) X * Like Loading... Related Tagged graph theory, puzzles, random walk 18 thoughts on "When random people give money to random other people" 1. Ryan Jones says: June 27, 2017 at 4:02 pm If this has some sort of relevance to what happens when people actually go shopping, I'm disturbed. 2. Rob says: June 27, 2017 at 4:47 pm But why do you call this a fair process? If you have $2 to your name, why is it fair for the Powers That Be to still force you to give a dollar away on the next tick? Maybe the question is "Why would this utterly unfair process be considered fair?". 3. williamsawin says: June 30, 2017 at 11:58 am In the large N limit, each round, an individual person gives up a dollar if they have one and then gains a number of dollars described by a Poisson distribution with expectation equal to the probability that any given person has at least one dollar. If p is the probability that any given person has no money, then the first process represents a loss of p+p^2 units of variance (It's equivalent to work with gaining 1 dollar if we have no dollars, where p units are lost relative to the old mean of 1, and p^2 more or lost when we shift to the new mean of 1+p) and the second process represents a gain of 1-p units of variance (the variance of Poisson), giving the equation p+p^2 = 1-p in the steady state, or p^2+2p-1 =0, so p =sqrt(2)-1. So the proportion of states where someone's out of money is not 1/e=.368..., but rather sqrt(2) -1 = .414..., slightly larger. 4. williamsawin says: June 30, 2017 at 12:05 pm (Sorry, I should have mentioned that this is in the case where everyone starts with no dollars, which you mention at the end). If p_n is the probability of having n dollars, then in the steady state we have p_0 = 1-p, p_n= sum_{i=0}^n p_{n+1-i} (1-p)^i / e^ (-(1-p)} i! + p_0 (1-p)^n / e^(- (1-n)) n!, and using this we can inductively calculate p_(n+1) from p_0,..., p_n to find the steady-state distribution. I don't think this is any kind of well-known distribution, but I could be wrong - there could be a more direct way to extract this from a Poisson distribution. 5. Spontaneous Inequality - Owen Biesel says: July 10, 2017 at 9:35 pm [...] will keep increasing until one person has everything. Jordan Ellenberg shares the insight over on his blog that this process is a random walk on a network where the nodes are distributions and two nodes are [...] 6. (Hua Xiang )Pin Fu noChai gaSheng mareruYi Wai naShi Qing gaDan Chun naShu Xue noShi Yan dePan Ming Zi You Jing Ji dakeziyadameda! - Feng noChui kumama says: July 13, 2017 at 8:51 am [...] When random people give money to random other people | Quomodocumque https://quomodocumque.wordpress.com/2017/06/27/ when-random-people-give-money-to-random-other-people/ [...] 7. [(Jing Ji )] (Hua Xiang )Pin Fu noChai gaSheng mareruYi Wai naShi Qing gaDan Chun naShu Xue noShi Yan dePan Ming Zi You Jing Ji dakeziyadameda!|donmainiyusuBie Guan 3Hao Guan |2chiyanneru matomeburogu says: July 14, 2017 at 8:25 am [...] When random people give money to random other people | Quomodocumque https://quomodocumque.wordpress.com/2017/06/27/ when-random-people-give-money-to-random-other-people/ [...] 8. [(Jing Ji )] (Hua Xiang )Pin Fu noChai gaSheng mareruYi Wai naShi Qing gaDan Chun naShu Xue noShi Yan dePan Ming Zi You Jing Ji dakeziyadameda!|2chWPdemoSu Bao says: July 14, 2017 at 8:55 pm [...] When random people give money to random other people | Quomodocumque https://quomodocumque.wordpress.com/2017/06/27/ when-random-people-give-money-to-random-other-people/ [...] 9. georgemarrows says: July 15, 2017 at 1:12 am @Rob - it's fair in the sense that everyone is treated and acting equally. Fair in the sense of a "fair coin". It's a mathematical thought experiment; there's no government or law enforcement making this happen. It says nothing about society and this isn't a libertarian's nightmare. @Jordan - thanks for the nice write-up. 10. randamuniXuan baretaRen garandamuniXuan baretaRen nioJin woDu sutodounaru ka? | You Look Too Cool says: July 15, 2017 at 5:33 pm [...] When random people give money to random other people | Quomodocumque [...] 11. [(Jing Ji )] (Hua Xiang )Pin Fu noChai gaSheng mareruYi Wai naShi Qing gaDan Chun naShu Xue noShi Yan dePan Ming Zi You Jing Ji dakeziyadameda! says: July 17, 2017 at 5:30 am [...] When random people give money to random other people | Quomodocumque https://quomodocumque.wordpress.com/2017/06/27/ when-random-people-give-money-to-random-other-people/ [...] 12. Rui says: August 5, 2017 at 7:10 am Shouldn't the edges of G be connected if you can get from one set to the next by all N people giving a dollar instead of just one random person giving a dollar? I can imagine some sort of theorem saying that both problems have the same stationary distribution though. 13. niyusuSu Bao | niyusuEr yoriSu Bao !Qi ninarukizinoJi Shi ! says: September 7, 2017 at 9:05 pm [...] Counterintuitive problem: Everyone in a room keeps giving dollars to random others. You'll never guess what happens next. - Decision Science Newshttp://www.decisionsciencenews.com/2017/06/ 19/counterintuitive-problem-everyone-room-keeps-giving-do... [...] 14. Aleatoriedad contra intuitiva - epsilon data labs says: September 19, 2017 at 6:24 am [...] problema lo encontre en este post, y si quieren explorar por que pasa esto les recomiendo este post. [...] 15. Start Up No.935: whither Windows?, the App Store subscription scam, China's Android schemes, the class news problem, and more | The Overspill: when there's more that I want to say says: October 22, 2018 at 12:01 am [...] usual? (From Decision Science News, a once-weekly signup newsletter.) There's more discussion here.link to this [...] 16. Andrew says: June 18, 2019 at 1:31 pm Related to Pareto distribution? 17. Random dollars for everyone ! | Freakonometrics says: January 19, 2020 at 7:22 am [...] I wanted to try, on my own, because I did not understood most of the posts. Because my first thought is that the problem is ill-posed. First of all, what is this "giving dollars"? is it a fixed amount or a random one ? Let us start by assuming that it is fixed. Now, if you know a little bit about gambling and ruin, you guess that it's very likelely that some one will get banckrupt (at least on a very very long range)... what should we do with that person? Actually, those points were clarified in Jordan's post [...] 18. [(ExcelVBA)] 100Ren randamudeShui kani1Yuan Du sumakurowoZuo tsutemimashita. | WORK NOTE says: July 20, 2021 at 7:49 am [...] WHEN RANDOM PEOPLE GIVE MONEY TO RANDOM OTHER PEOPLE [...] Leave a comment [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] - Previous post Next post - Recent Posts * A fang, a feeling, a flair, a match, a thing for you, levitation, my TV and my pills, New York * Brewers 5, Orioles 2 / Orioles 8, Brewers 4 * That's when everything went widdershins * Get out of my dreams * This and that * A paleontologist, a scientist, a tree, decided, God, Superman, the leveler, the voice of Sarah Strickland's rage, the walrus * St. Olaf, Carleton, UW-Madison, wholesomeness * Another thing about the White Lotus * I Just Saw a Face * In which I have cursed the Baltimore Orioles Recent Comments * JSE on A fang, a feeling, a flair, a match, a thing for you, levitation, my TV and my pills, New York * Brett Yost on A fang, a feeling, a flair, a match, a thing for you, levitation, my TV and my pills, New York * burrobert on A fang, a feeling, a flair, a match, a thing for you, levitation, my TV and my pills, New York * tsundoku on That's when everything went widdershins * just different on That's when everything went widdershins * George J.R. on St. Olaf, Carleton, UW-Madison, wholesomeness * quasihumanist on St. Olaf, Carleton, UW-Madison, wholesomeness * George J.R. on A paleontologist, a scientist, a tree, decided, God, Superman, the leveler, the voice of Sarah Strickland's rage, the walrus * St. Olaf, Carleton, UW-Madison, wholesomeness | Quomodocumque on Writing exercise: poll report as dialogue * allenknutson on I Just Saw a Face Top Posts & Pages * When random people give money to random other people * About * How Not To Be Wrong * Mochizuki on ABC * Booklist 2011- * A fang, a feeling, a flair, a match, a thing for you, levitation, my TV and my pills, New York * Ellenbergs * Tips for giving talks * Why won't anyone teach her math? * Lo! Blogroll * @JSEllenberg at Twitter * Cathy O'Neil * Crooked Timber * Emmanuel Kowalski's Blog * Gelman blog * God Plays Dice * Gowers's weblog * Lacunae * Letters from a broad... * Light Reading * Malvasia Blanca * Persiflage * Tea, Lemon, Old Books * The Value of the Variable * What's New ab academia bad statistics baseball blog books cars children cj college comedy commerce computers economics education ethics family food friends harvard history how not to be wrong language lists madison magazines math movies music news nostalgia offhand orioles papers philosophy poetry politics psychology recipes shows slate teaching travel Uncategorized writing Search for: [ ] [Search] RSS Feed * RSS - Posts * RSS - Comments Blog at WordPress.com. * Comment * Reblog * Subscribe Subscribed + [wpcom-] Quomodocumque Join 1,035 other subscribers [ ] Sign me up + Already have a WordPress.com account? Log in now. * Privacy * + [wpcom-] Quomodocumque + Subscribe Subscribed + Sign up + Log in + Copy shortlink + Report this content + View post in Reader + Manage subscriptions + Collapse this bar %d [b]