5

I have a fold up table at home with six legs and three areas. Each area takes 2 legs to keep the table up, but when stored three legs are positioned on the left and three on the right.

Everytime I setup the table I randomly take the three legs on the left, put two on the left side and one in the middle. Then I take the three legs from the right and put two on the right and also one in the middle.

When folding it up I randomly pick one leg in the middle to go left and one to go right.

So basically a leg that started on the left when folded, could end up in the middle when setup and end on the right when folded again.

I've setup this table maybe a hundred times and everytime I wonder "Has each leg been in every spot (six spots when setup) at least once?"

I guess there is a 1/3 change that a leg ends up in the middle and then a 1/2 change it ends up on the other side, which by my uneducated mind results in a 16.6% probability it changes sides, but I have no idea how to go from there.

If you perfectly rotate the legs around, you could get them in each spot in 6 times. But I don't know that is even relevant at all.

So, what is the probability each leg has been in every spot?

Bernard
  • 175,478
Hugo Delsing
  • 103
  • 1
    Are you looking for an exact answer or an estimate? $1/6$ is a pretty big number - after $100$ setups each leg would on average have swapped Left-Right $100/6 \approx 17$ times, and a leg starting on the Left would have spent almost equal amounts of time on L vs R. And with $\approx 50$ setups from each side, chances are also very good it would have been in every spot from that side. So my estimate would be close to $100%$. But of course this isn't an exact answer if that's what you want. – antkam Oct 05 '19 at 16:22
  • I guess a more mathematically interesting problem is to construct a Markov chain like model and to find an expectation of number of table setups before it will happen that each leg been in every spot at least once. – Alex Ravsky Oct 06 '19 at 21:55
  • I was looking for a way to get to an exact answer. How would you go and calculate something like this and which variables are important and which are not. – Hugo Delsing Oct 07 '19 at 16:36
  • If you want an exact answer, the only way I can think of is a Markov Chain, but the chain I have in mind would have a lot of states. Basically the full state is described by, for each leg, which subset of holes it's visited. So that's $2^6=64$ different states for each leg, for a total of $64^6=2^{36}\approx 69$ billion states (or $64$ $giga$states :D ) Maybe Alex has a better (more compact) idea... – antkam Oct 07 '19 at 17:45
  • OTOH if you want to know if a specific leg (say, one with a dent) has visited all 6 holes, that's a much smaller Markov Chain, and might be fully analyzable by hand. However, I dont think it is simple to find the exact answer for all 6 legs based on the exact answer for 1 leg, because the legs are dependent. – antkam Oct 08 '19 at 04:32
  • It seems it's not the simple calculation I expected. If you could write an answer for one leg, or atleast the steps to follow, and some explaination I'd be happy to award the credits – Hugo Delsing Oct 09 '19 at 08:18
  • @antkam There are many different symmetries that could be exploited to cut down on the number states. I wrote a program that calculated the different number of states that can be reached (modulo symmetries) and found it to be 20109024. If my calculations are correct, then the probability would be feasible to calculate. – Pazzaz Jun 06 '21 at 17:53

3 Answers3

3

Suppose the legs are numbered and ordered in a list, for example [1,2,3,4,5,6]. When packed away the first three legs in the list are on the left, the last three are on the right. When erected the first two are on the left, the middle two in the middle and the last two on the right.

Let's consider the possible permutations that occur between a table being packed away and then re-erected. If we start with a table with the order [1,2,3,4,5,6], the possible orders after being packed are [1,2,3,4,5,6] or [1,2,4,3,5,6]. After being reassembled the 18 possible permutations are:

P = { [1,2,3,4,5,6], [2,3,1,4,5,6], [2,3,1,4,5,6], [1,2,3,5,4,6], [1,3,2,5,4,6], [2,3,1,5,4,6], [1,2,3,6,4,5], [1,3,2,6,4,5], [2,3,1,6,4,5], [1,2,4,3,5,6], [1,4,2,3,5,6], [2,4,1,3,5,6], [1,2,4,5,3,6], [1,4,2,5,3,6], [2,4,1,5,3,6], [1,2,4,6,3,5], [1,4,2,6,3,5], [2,4,1,6,3,5]}

As some commenters mentioned, working out precisely the expectation that all legs end up in all spots is (probably) very hard, but I think this is a great example of a situation where running randomised simulations in a computer should give a pretty good real world answer.

For a given number of disassemblies and erections between 1 and 100, I ran 10000 simulations and counted for how many simulations each of the legs occurred in each of the positions. The results:

enter image description here

So, if you have setup the table 100 times I would say it's very likely indeed (> 99%) that all the legs would have been in all positions!

JMP
  • 497
  • 3
  • 12
  • 2
    +1 for probability of success as a function of erections – Benedict W. J. Irwin Oct 11 '19 at 13:19
  • It's friday. My only regret is not labelling it as successful leg positioning.. – JMP Oct 11 '19 at 13:25
  • I am quite surprised that with as few as 20 setups, there is already an appreciable prob (looks like ~8%?) of all 6 legs visiting all 6 holes. (I would also guess this is helped by the legs being dependent: i.e. if one leg has visited all holes it slightly increases the prob another leg has visited all holes...?) – antkam Oct 11 '19 at 13:45
  • @antkam I actually counted the number of legs to visit a hole, rather than how many holes each leg visited, so can't quite give you those conditional stats. However, after 20 setups the probability of one hole being visited by all legs is very high (> 95%) however the prob of all six holes being visited by all legs is only ~6%. – JMP Oct 11 '19 at 14:10
  • you had to track which leg visited which hole, right? so theoretically you could answer both "who visited this hole" and "where has this leg visited" questions. but to be clear, i'm not asking you to write new code! :) mine was just a comment. your observation of the 95% is also much higher than i thought, and therefore interesting. i wonder if there is some sort of "leg-hold duality" ;) that could convert one answer to the other! – antkam Oct 11 '19 at 14:35
  • @antkam ok let's race. 40 erections. 1000 times. Which is greater average: Legs that visit every hole, or holes visited by every leg?? – JMP Oct 11 '19 at 14:51
  • LOL, ok, if i am gonna bet i might as well bet on my belief (even without any good justification). i bet duality holds and the two numbers are "about" the same, lets say, $E[X]$ is within $E[Y] \pm \frac13 \sigma_Y$ and vice versa. – antkam Oct 11 '19 at 14:58
  • Legs: 5.445. Holes: 5.451 :) – JMP Oct 11 '19 at 15:08
  • 1
    haha, so ...uh... I win? – antkam Oct 11 '19 at 16:47
  • Probably the best answer to this question and love the graph thanks! – Hugo Delsing Oct 13 '19 at 06:37
  • Why isn't [2,1,3,4,5,6] a possible permutation? It's like you treat each side as its own (sorted) set but we care about permutations that switch legs even if they're on the same side. – Pazzaz Jun 18 '21 at 11:32
  • 1
    @Pazzaz good question! Initially I thought it was just a typo, as [2,3,1,4,5,6] appears on my list twice, but looking back now I would say that there should be 72 (2 x 3! x 3!) permutations, not 18. In my program I would likely have used a permutation iterator, but I no longer have the code so can't say for sure. Either way this answer patently contains an error! I will edit when I have time but feel free to post a better answer. – JMP Jun 18 '21 at 13:17
1

Solution for one specific leg only. (Note: It is not obvious, at least for me, how to generalize from one leg to six legs, coz the legs are dependent. In other words, @JMP probably used code that has way more states than this solution.)

The following Markov chain will model moments when the leg is stored. The state is $(x,y,z,b)$ where:

  • $x,y,z \in \{0,1,2\}$ represent how many spots it has visited in the Left, Middle, Right pair of holes respectively, and

  • $b \in \{L,R\}$ represents which side its being stored.

  • We start in state $\{0,0,0,L\}$

Consider a generic state $(x,y,z,L)$ (the $R$ case is symmetric).

  • There is $2/3$ prob it will visit one of the Left holes. Conditioned on this happening, the next $b = L$, and $x$ will increment or stay the same:

    • $x: 0\to 1$ with prob $1$

    • $x: 1\to 2$ with prob $1/2$

    • $x: 2$ cannot increment

    • We can summarize the above by saying $Prob(x \to x+1 \,\,\text{i.e. increments}) = 1 - x/2$, and similarly $Prob(x \to x \,\,\text{i.e. stays constant}) = x/2$.

  • There is $1/3$ prob it will visit one of the Middle holes. Conditioned on this happening:

    • The probabilities for $y$ to increment are analogous to above: $Prob(y \to y+1) = 1-y/2$

    • In this case the next $b\in \{L, R\}$ with $1/2$ prob each.

So collecting everything together in terms of transition probabilities:

  • $P((x,y,z,L) \to (x,y,z,R)) = \frac13 \frac12 {y \over 2}$

  • $P((x,y,z,L) \to (x,y+1,z,R)) = \frac13 \frac12 (1 - {y \over 2})$

  • $P((x,y,z,L) \to (x,y+1,z,L)) = \frac13 \frac12 (1 - {y \over 2})$

  • $P((x,y,z,L) \to (x+1,y,z,L)) = \frac23 (1- {x \over 2})$

  • $P((x,y,z,L) \to (x,y,z,L)) = \frac23 {x \over 2} + \frac13 \frac12 {y \over 2}$

    • Note: the first term is the sub-case of visiting an already-visited Left hole, and the second term is the sub-case of visiting an already-visited Middle hole.

  • Sanity check: the above $5$ probabilities sum to $1$, whew! :)

So we have a Markov chain with $3 \times 3 \times 3 \times 2 = 54$ states, where each state typically can reach $5$ states (including itself), but sometimes fewer (if some of $x,y,z$ have maxed out). What you want is the time $T$ (i.e. no. of steps) to go from $(0,0,0,L)$ to $(2,2,2,b)$ where you don't care whether $b=L$ or $R$. You specific question is the value of $Prob(T \le 100)$.

This kind of problem is well studied (I've seen it called "first visit", or "time to absorption" if you combine $(2,2,2,L)$ and $(2,2,2,R)$ into a single absorbing state). IIRC closed form solution is possible...? But of course the issue is that, without further insightful tricks, the transition matrix itself is complicated, so even a closed form (based on the matrix) will still be complicated.

antkam
  • 15,363
1

I have calculated the exact probability that all legs have visited every position after 100 steps — using a computer program (which I hope is correct). It's a rational number with denominator $144^{100}$ and numerator $$ 685450342984768896102517503367820496154926677485999771971661125684196228413486018656572896834702335992482035092552092446349393062462012808134805846946924485527177360661043864592468174484909265410054449252423330901632 $$

which is approximately $0.99937110522969475193$. So you can be more than $99.9\%$ certain that each leg has visited every spot.

Here is a graph of the number of shuffles vs the chance that all legs have visited every position.

enter image description here

This was found by treating the problem as an absorbing Markov chain problem where every node is a state specifying where the different legs have been, and every edge is a transition that can happen after a shuffle. To reduce the number of nodes, we only have one node from every equivalence class of symmetries. So flipping the table around, switching the right legs, switching the middle legs, etc. are not treated as changing the state. The total number of states was $20109023$. This was still a lot but manageable with a good computer and a couple of days of computing time.

To find the probability of ending up at the state that represented "all legs have visited every position" after $k$ steps, we create a state vector with a one in the starting position, multiply that vector $k$ times with the transition matrix, read the value in the vector that represents "all legs have visited every position" (the absorbing state) and then divide it by $144^k$. The code can be found on Github and the raw data (up to 104 shuffles) is below.

Each row is the value in the state vector representing the absorbing state, starting at $k=0$ shuffles. Divide by $144^k$ to get the probability of absorption.

0
0
0
0
0
32
144976
465294048
818785941504
852435535987216
593951600665835312
305761728933995329616
124963475315933274299024
42705003951428519877131712
12675097687217289970627019728
3361114621908770805972554374160
813571117508982731861705034251040
182758582092944840829431773227464000
38597314446945857877460330518454064304
7742723444573966247683766155122063898208
1487521644288286071010269474200384615043360
275524905716145486295698713830189835532458336
49471129163982910663444533447907455441199074320
8649370048622971220144251328607790678233456509328
1478003659086679243223315395823276080846118172025808
247614195373829130969272197465849784914575440948402912
40777441270014446785963125486443017236983183727380296192
6615593427558096883604581322213868793865777846404503438640
1059346643459880590186410281386020842946800145931145028872800
167696877320802388894434912759271908244935986595195007468666592
26280146349644664796655601439189997340515472940495601774149721280
4081899029700028215977934142919969314843201431893796077002134481504
629034959827965077511160424620378575027461642642965396526677263257408
96261614804958649440445041367589369849369486034655318050015648616828368
14639809367648356818416832774356946411026785486656951663514087958272604688
2214202533748420572952248565051348049425587240946708488188518991260102638832
333240959528353959566419778330679087756181968708864996390728337426451539748912
49932904710551987645739653457096566423723293584403501434024276548017144232617232
7452536935203182005552780246058084267881644681547510674178842078132689931142994688
1108379415349063055360461436586218405681973290356330831830732929569803946952969641104
164322754750928201293481424627404303702894642756598145141321773561572211283739849740560
24292499725913460607215940909487966179956948983398337614705392311715232515012865658926176
3582092828302739220456470243005890078093321300836413303436710179005204096461210123409446576
526990710549164030165401572963280106088534265379607332173065326417595767234154275025344913504
77369545884649516453208296314240471431036460139843826118897752147296005746899751338036879299232
11337755377523836683025783511617381199106185264351997928611474782733303834033586765232838571098864
1658646261682481382378441010849911703145543674679011785542094645418168210788168051054299403254714256
242282261071496671155924780199083574560469725862462598586598306762371376394317113853569787864068564576
35342300360010735188134407833127473838202785825372480887552591306028544443654124648673167136797958228832
5149096950341885579170556425632701056713378987637668277845452502418421868426038653206967733612674664538912
749345851029615598491978567790780534025044093780894073247801837714418538647273812279863543492105721597821712
108941984634970885758858462784372652033493695352281763710111870502244868293739157366635699144126803262198749040
15823849007045221962104093297505821760189364869485524019111120889753661188532255168010820415322449855073860197504
2296523239944961439543068962031562641649545673030743410308292969541142994994394321618577989020227040333216356755024
333047140554094352224687149138004725338783096649465800644426496926639710811026354371090837457909888221053131835044176
48266707432369277436578970542726077859423011652299971910448274288306903366855231033602712134531916844215996904495347376
6990764824232575411636744038833582510391374798512412349475309575874982702708322608349928174985370974527355556791707740720
1011956913969746514788781635475268327673856878459222929343143641815555464819945392928590740151079987099064520981823576025936
146413961831788900295593880627808089429156763217657089376622632930722890437590399320794194221352887396678777740651401933613744
21174187020467415851664226475215841156031458316693069599741398274738303998288552162086097763593758977359821790293330060948923952
3060930337373864754110253148044070316373201543123992265753383707894821484747485963934245545982373721074665463718063736355075385344
442322958005026083811793431098605543682151673206007972710780612514995412318775987568358925578048152073607485779468283795138311212272
63896949926419087361143973028512141608119150125395725049448733153171762050996158140985222149959927471486906664679120506399359980010800
9227609534106826275313778790098269047605942524239263242877853000238528827200111413747021580075172096911005070300523262388206996481510960
1332230077279597230316515517831561370302852418873090707059584561739335686332132733257201586996629595611229023301143858806371100774470818352
192292136817678180947734154415079291787221322194680420754274665279044463973551676470724989590127374697005580415879393308533092965148681575152
27748935664258214488328488019234649237176654780329854553039285754940568323301263836412997634195507871853824339022790928419994638425175922206864
4003528490547489550903890039501867205717667900830592620364964154009624709504907363914033912862707653197348434525268403656227101321726263718459696
577510256755417912480644592396677140646986744132775306106741158421105707935001912273383470314062434005471601961636206773509324022152359104377095616
83292186946089885619894474598967004902434720176088305076605651909174197451515800202529780582344506300518210742110744144004175737050590221709123589856
12011119645107152859647498985369345542317685113920027473232788551503154113984142312077509492647095222290594709578405895542858257712311469289694987667584
1731823436825896893427028148165304659796702027034669265315088338130983059327367787261892105085549784812060019043888837885205927091100148690362228778343504
249672241682377303882661727606620902154468413183663605012749768507813833276230790514898709173497754140932865322181639693046141602439236657767806485056261440
35990554579743347050314911391588492231124452601624439053045811015100399325706298792506751763593622811925547304809269448867680450245881734247192782301687362096
5187559188084995473416945716980703107058627833621036845208632315612854849231396358199414371316707877486938068616792235507904482631143859859464848991237667833984
747649450126907753315374962691620146485840822940763946145610865040267357635974438528085937614147652748934580493949247050905828961487419525447287522411821191879376
107745013798095134729410900535923268884193172114878275711747457045314895375756390766951356720809134775555057453075676635378796822822016447477401756562793372192248656
15526157102395522665996655651164943724321414118915926450037503384886278454935933079953318923609383418356357826758536782856419598790772134297269683258005938030946787056
2237182951259182412504413147441017514955057456751137578820563516916417936100101487473768627943189657348353739824993484476707786587416539627111512748846643920491023590720
322338780139207850221963179555899850485144821495849976442621406724885425157852352081522296847424605973988193260076581734742168344563960655271200112202169789183242510623376
46440798984124390207042889367267496534525304560426825396139407088009319848294425249041583480544042902296246371992948184976480834435171751092611775243795360962669485282813856
6690601595494325704933134333952707276199674969284513563149789378377497449801188584416543179934566681747055218404512153256784896527817200833043703499149041208338098394436657792
963853644980769674950872888726198126998524277036964256117133341539598511263104529601768818254154959906630861327367720750172073701244620659418091674282512359562588491739036232976
138847905606602615199087552784311857738220955634697019435414891711965864831087907654551891202542318641238887963205304938116698259340934224183109557674909083195091600770253960372656
20000994266575575309364929134320635955507002846240723994408570975812664283917226872848216977480788653024441075324171787980301774731649148051501211906888520042187825904973181383665680
2881040653170529416327990794300236524875649379120930691094395692621119459061179041482321017620490425646769004957219759046303961558424110654937769838059374147746323681006087481552916880
414986649893061550348638512168630620069596452131896561218985253732632861137664157063037894095947671271393041736185485773920566857099529168448703023484952647496008148637328560305074119568
59773276051373519106086261653449536366993362739052897877820702336701612713312907606966434078307654997417219118814331792246389669194246036746164223242525399383527972009513398038224522972192
8609329372975868822576490301419972185171254298314142192419877815601319745321734001940523402588020117589321403024906016099074226350449669865927701042522410946025519952005425477937412518031552
1240000741231406446002044161121225432908149501245307781595135194197665900243560593358300853748148524153266267699709777401757901749285508977271631249892543741798108425349017346113233309906961392
178593583960748356009601887136589215577061776669029417990359277221498141133281373676661381688672441496674446297350523093436847940396006944504322625989996486479043453005190788510649287303460072192
25721831361524839578159527819944441701312575360684310406550097565502523855662297480953635003912291869272553941345649077767146662499804744357495248583818059966738956719548176300783573958889560161040
3704510291669504842816246084880913773657780264323885556485458748511207109747205273539454117397105415978065647331316652352173371597834833752855776618946060527058868961550778101745208971601029989470944
533523183902213452043056605237317753902963213570234580543358131289594697502642542262081065344829324137526378238444591044448669483034156496643599117059550741505200285173389844161399324008306793818825264
76836925395708583842876867295908800303548029066250159202673031786441697301138438251636306369343767735603292021027403025380384804398200739660565864197011537565442491977213623059800181939045001655939797296
11065764236572445507949035454322387466737379080242114091983286416198870904754170435798700557217354082138737726911546811890036130929418196775166321663145387203346351269629856818113409667480114141780331528768
1593632239024478475321338210809541795729172777875088803058223186006583725959076891269886059578661127542926957981679839018705416350846517452772519692653267302763117104720448290116077210088008858593117385518624
229504136742571840571020060652329227615511011628019107962198109712667376697869187549255958945834884140750828310612178252168567393650385149009270636493876933449568257049721121642676337717827212418932556658374176
33051339116412923528687978293925926279607992751674125530441422962677968052115790367649761125613575826660548002229772855992925968302094658140753405832689531668518486295761932318040055529807118322598847858602316704
4759749616337650102543020821941073742320140276137262794956517731725743569203893753679541902266097025028899099094392073960230873758360086482529167972020586064831190165792177826145426623644823546470366398230961030912
685450342984768896102517503367820496154926677485999771971661125684196228413486018656572896834702335992482035092552092446349393062462012808134805846946924485527177360661043864592468174484909265410054449252423330901632
98710883089014244841892068145522621306493251549464876559767518575278451490735422380276443508799769872652530487539701883447439101384487208242332216134671834571564001623172861449364921279376228847346763091462719113151552
14215151771888686271552605386775406681826551475189466637630272437387243871427918743450312326789293493373906285329052176236951561936978830561067470538577198266357980431016477426700794354753950847171295799673738826443375040
2047083880427387411901032550718788112634090615531863179222786297708845588274570914424684885337551618109441816808860454678452464993063737759308177741759380056747641294600207250796453353300863417338408128769609987233682481840
294793345116238181847244736331185257791506385486955685698014807386965117633113389138450458120890720619704141361675784097842001474888250713857868963079675238109457706001272464643672188133509997729961994280031683963697218491328
Pazzaz
  • 664
  • 1
    Thank you for another fine solutions. The 99.999% was bugging me so I manually rotated all legs and now i'm 100% sure they were all in every spot ;) – Hugo Delsing Jun 22 '21 at 09:46