Zachary David's – Market Fails & Computational Gibberish_News & Media

Zachary David'sMarket Fails & Computational GibberishZachary David'sMarket Fails & Computational GibberishBlogAboutContactQuick Post: “n people line up to sit in an n-seat theater”July 20, 2018by Zak5 min readAdd Comment Quick Post: “n people line up to sit in an n-seat theater”Let me count the waysWith a Nod to SchellingOn Twitter, Josh Wolfe posted the above problem, which asks:100 people line up to take their seats in a 100 seat theater.The 1st person in line lost her ticket and so sits in a seat at random.Each remaining theatergoer sits in their assigned seat unless it’s occupied, in which case they sit in a seat at random.What’s the probability that the last person in line sits in their assigned seat?In the responses, the set of answers is about what one would expect for a somewhat subversive question such as this — with the most common mistake being 1/100 = 1%. Other kindred spirits estimated the correct answer by writing code to simulate the above scenario and watched how it converged. As someone who likes to simulate everything, I think that’s a reasonable play. But in this case, out-right simulating the above scenario doesn’t give much insight into the underlying problem, so it’s easy to miss the main takeaway: it actually doesn’t matter how many people/seats there are, the answer is always the same.1First, approaching these sorts of problems is almost always easier when they’re phrased in terms of counting things rather than probabilities. So what are we counting here?The number of ways to fill the seats so that the last remaining seat is the last person’s assigned seat.The number of ways to fill the seats so that the last remaining seat is not the last person’s assigned seat.The relative frequencies of each of the previous outcomes.Since the last remaining seat is either the last person’s assigned seat or not, (1) + (2) = the total number of ways to fill the seats. The number of combinations in which persons A through n-1 can choose a particular seat determines its relative frequency — e.g. if there are 3-seats, person A ends up in each seat 1/3rd of the time, but since they can end up in seat 2 in two different ways, person B’s choices then split those odds. Then summing over (3) for the last person’s correct seat assignment is the probability that the last person is in their correct seat.Next, it’s almost always easier to count smaller things than larger things. When working with several small cases that are easy to visualize, relationships between the cases will often become apparent. In combinatorics, a recurrence relationship allows us to get the solution for the n+1 case by knowing the solutions for the smaller cases.2 So instead of jumping directly to the 100-seat scenario, let’s look at simpler scenarios:Let person A be assigned seat 1, person B be assigned seat 2, person C be assigned seat 3, etc. (without loss of generality)In the 2-seat scenario, person A randomly takes either seat 1 or seat 2, and then person B must take the remaining seat. The possible outcomes are then:2-seat theaterIt’s easy to see that the probability of person B sitting in their assigned seat is then (1/2).When we move to the 3-seat theater, if the first two seats are filled according to the same pattern as the 2-seat scenario, then the only remaining option is for person C to sit in seat 3, and thus person C sits in their assigned seat in both cases. But there are also two new possibilities for persons A and B to fill the seats:3-seat theaterAnd again, the probability of person C sitting in their assigned seat is (1/3) + (1/6) = (1/2).It turns out this pattern continues to hold. When adding a new person/seat, the first n-1 seats are either filled according to the n-1 case, in which case the new person must sit in their assigned seat, or the first n-1 seats are filled in such a way that seat 1 remains empty and the last person must sit in it. The sum of the relative frequencies of those two possibilities are equal at (1/2). To highlight the pattern:4-seat theater(erratum: special thanks to Kid Dynamite for pointing out two errors in my original 4-seat chart, and then another one in my first correction)Each of the things we’re counting in (1) and (2) are then equal and grow at the same rate. Thus, the probability is the same no matter what n we choose.This exercise reminded me of some examples in Thomas Schelling’s Micromotives and Macrobehavior where there’s non-obvious, invariant aspects to different types of counting problems. I’m out of town now but I’ll update this with some specifics later.edit: It’s March 2019 and I did not update this post with some specifics later. If that ever happens, I’ll make a big deal out of it.____Thanks to Jamie Pastore for just being Miley.This post originally appeared on Zachary David’s Market Fails & Computational Gibberish.123…14Next Last Tweet (@ZakDavid)@Taylor_Fritz97 Congrats!, Recent PostsQuick Post: “n people line up to sit in an n-seat theater”Quick Post: Misrepresenting Evidence In Behavioral Finance/GeneticsAccountability, Generalizability, and Rigor in Finance Research: Machine Learning in Markets (Part II)Fitting to Noise or Nothing At All: Machine Learning in MarketsNGDP Futures Targeting Is A Pretty Goofy IdeaIntroduction to Agent-Based Models with respect to the Future of MacroeconomicsKnow Thy Model: Specificity and the Importance of Using Fake DataOn HFT (Part III): Still confused about high-frequency trading? YesOn HFT (Part II): Bugs, Features, and Aggressive IncompetenceOn HFT: Assumptions, Agent-Based Modeling, and a Philosophy of ErrorRecent CommentsAI and Deep Learning in 2017 – A Year in Review – WildML - BusinessXM on Fitting to Noise or Nothing At All: Machine Learning in MarketsAI and Deep Learning in 2017 – A Year in Review – WildML - Business 2020 on Fitting to Noise or Nothing At All: Machine Learning in MarketsSRZ on Accountability, Generalizability, and Rigor in Finance Research: Machine Learning in Markets (Part II)Fitting to Noise or Nothing At All: Machine Learning in Markets – Zachary David's on Accountability, Generalizability, and Rigor in Finance Research: Machine Learning in Markets (Part II)ZHD on Accountability, Generalizability, and Rigor in Finance Research: Machine Learning in Markets (Part II)ArchivesJuly 2018June 2018January 2018August 2017July 2016October 2014May 2014April 2014March 2014December 2013July 2013May 2013August 2012Om Nom NomAdam CalhounAndrew GelmanBeatrice CherrierBrian RoweCathy O'NeilClaudia SahmCorley MillerDaniel LittleDeborah MayoEmanuel DermanEric FalkensteinErnie ChanFrances CoppolaGary BasinGeorge ShiberJen GunterJohn AzizLior PachterNoah SmithPeter WoitRick BookstaberSabine HossenfelderScott AaronsonScott LocklinSean CarrollSteve WaldmanMetaLog inEntries feedComments feedWordPress.orgCopyright © 2022 Zachary David's | Developed by by Zealopers. BlogAboutContactFacebookTwitterGoogle Plus