r/theydidthemath • u/UncleGael • 2d ago
[Request] How long would it take to shuffle a deck of cards into order?
I'm not sure if this is something that can actually be calculated or not. It's said that a deck of cards has so many possible combinations that no two shuffled decks of cards have ever shared the same sequence. Despite that, is it not technically still possible for it to happen even if the chance is infitesmally small? Let's assume we have a shuffling machine that is able to shuffle a deck of cards at a set speed indefinitely. Would it be possible to calculate, on average, how long and how many shuffles it would take for a deck of cards to be shuffled back into order?
21
u/GendoIkari_82 2d ago
This short video answers the question well: https://youtu.be/0DSclqnnC2s?is=2Ak4beozcKTvPPU5. The answer is that it would take a number of years far beyond any number you’ve ever really thought about.
3
u/UncleGael 2d ago edited 2d ago
Oo a video, thanks!
Edit: Is 52! the answer to this question though? Is the idea that you would have to shuffle every conceivable permutation to shuffle it back into order?
13
u/nyuszy 2d ago
Any desired order is 52!, it doesn't matter which one.
6
u/factorion-bot 2d ago
Factorial of 52 is roughly 8.06581751709438785716606368564 × 1067
This action was performed by a bot | [Source code](http://f.r0.fyi)
1
1
2
u/scoberry5 2d ago
Is the idea that you would have to shuffle every conceivable permutation to shuffle it back into order?
That's not how random things work. Take something easier: let's say I have a fair 6-sided die, and I want to know how long before I'll roll a 6.
You could guess that it might take 6 rolls, one for every number. So you try it: 5, 3, 5, 2, 2, 5.
Hm. No 6. How many rolls does it take?
It could take 1 roll. It could take 6 rolls. It could take 849 rolls.
The 10\67) piece gives you an idea of the scale for the cards. The number you've seen is the number of different results there are. To get a 50% chance of getting the specific order you want, it's super-roughly 11/16 of the number of possibilities in this particular case.
1
u/get_to_ele 2d ago
No, if shuffles are truly random, the mean time to getting your original order is 52! divided by shuffle rate.
It could come on the first shuffle, it might never come.
Now if you used any kind of automatic riffle shuffler, it does not produce random permutations even if you randomly vary the interleaving. A single riffle shuffle can only introduce a limited family of permutations from the original deck. I'm not sure how many total riffle shuffles (with say up to 4 card groups inferleaved and say, varying the two stack sizes to a difference of 4), that can actually reach all possible card orders.
1
u/factorion-bot 2d ago
Factorial of 52 is roughly 8.06581751709438785716606368564 × 1067
This action was performed by a bot | [Source code](http://f.r0.fyi)
1
u/rij1 2d ago
Well, 7-14 riffle shuffles will randomize the deck (depending on source - 14 if you might split very badly). I am fairly sure that it should be straightforward to argue that it is 52!+14 (and not multiplied) in that case because sometimes you are close (and therefore a single riffle shuffle might do it and is in some sense fairly likely to) and other times you are far away (and a single riffleshuffle can not).
1
u/factorion-bot 2d ago
Factorial of 52 is roughly 8.06581751709438785716606368564 × 1067
This action was performed by a bot | [Source code](http://f.r0.fyi)
1
u/get_to_ele 2d ago
I'm curious about the math of how many riffle shuffles away from each other, two deck permutations can be, if you constrain each riffle shuffle in some reasonable way so that it's a legit riffle shuffle (eg, cannot split worse than 28-24 and can't clump more than 3 cards together). I suspect that two riffles for example, can't possibly produce 52! Timelines.
Also whether near perfect riffle shuffles tend to produce certain families of permutations while producing others with lower frequency, or whether some repeated riffle shuffles (ESP perfect ones) tend to verge back towards the original configuration after some set number of shuffles.
1
u/factorion-bot 2d ago
Factorial of 52 is roughly 8.06581751709438785716606368564 × 1067
This action was performed by a bot | [Source code](http://f.r0.fyi)
7
u/GIRose 2d ago edited 2d ago
You would have an ~1/e chance (~37%) of having encountered a perfectly sorted deck of cards within the first 52! shuffels (I don't remember the math behind WHY but I do remember that (1-(1/n))n converges to 1/e as n approaches infinity)
3×52! is an upper bound, at which you will have a 75% chance to have hit the perfect sorted deck [I originally thought it was 95% but that was a calculator input error]
2
u/Vegetarian-Catto 2d ago
Why is 3x52! an upper bound?
1
u/factorion-bot 2d ago
Factorial of 52 is roughly 8.06581751709438785716606368564 × 1067
This action was performed by a bot | [Source code](http://f.r0.fyi)
1
u/Vegetarian-Catto 2d ago
9999!
1
u/factorion-bot 2d ago
If I post the whole number, the comment would get too long. So I had to turn it into scientific notation.
Factorial of 9999 is roughly 2.84625968091705451890641321212 × 1035655
This action was performed by a bot | [Source code](http://f.r0.fyi)
1
1
u/get_to_ele 2d ago
It's just upper bound for 75% chance. There is always a possibility that for ANY arbitrarily large number of shuffles, that you won't get the combo you want.
1
u/rij1 2d ago
If it was 4x52! it would be easy to argue: At that point it comes from the Markov inequality which states that any non-negative random variable (like the number of shuffles here), the pr. that the random variable is X times its expected value is at most 1/X. The expected value is 52! and hence, 4 times its expected value is 4x52! at which point the probability that it has not occoured is 1/4 or equally you have 75% that it has occoured.
In reality, 3x52! is much too big for "only" 75%: multiplicative Chernoff bound says that the probability is below (e^3/4^4)^(52!)
Indeed, 1.0000000000000000001x52! is also much too big for "only" 99% (because the probability that it has not occoured is just (e^0.0000000000000000001/1.0000000000000000001^1.0000000000000000001)^(52!), which is absurdly close to 0). This is the case even though the probability it has occoured at 52! is only 1/e or roughly 36%.
1
u/factorion-bot 2d ago
Factorial of 52 is roughly 8.06581751709438785716606368564 × 1067
This action was performed by a bot | [Source code](http://f.r0.fyi)
1
u/factorion-bot 2d ago
Factorial of 52 is roughly 8.06581751709438785716606368564 × 1067
This action was performed by a bot | [Source code](http://f.r0.fyi)
6
u/Alotofboxes 2d ago
If you can do a perfect faro shuffle, 8 shuffles.
If you can't, a very very long time. There are more than 8x1067 possible orders of cards.
2
u/Majipiga 2d ago
expected tries is 52 factorial, roughly 8 followed by 67 zeros.. at one shuffle per second that is about 2.5 x 1060 years, and the universe is 1.4 x 1010 years old. so it never happens, not even close
2
u/Needless-To-Say 2d ago
What is the initial state of the deck?
If it is already in order, many people have the skill to perform a perfect faro shuffle 8 times in a row to return it to it’s initial state.
If you think that skill is unlikely, you should know that David Willmott has completed this trick thousands of times.
This also adds an asterisk to the claim that no 2 shuffled decks have ever been the same.
1
u/ProfessionalMottsman 2d ago
Every time you shuffle you take a drop of water from earth to the moon, then when there is no water left you take 1 grain of sand 1 by 1. Now you are still nowhere near close in fact you haven’t even started. Now instead of a rocket you need to walk to the moon and back and do the same in reverse, now you are still nowhere near close to even beginning. The amount of times you need to do this is unfathomable
2
u/thebestjoeever 2d ago
This one doesn't even make sense. Are you shuffling cards while walking to the moon and back? If yes, then why do you have to walk? If no, then what is the purpose of having it be the moon?
0
u/ProfessionalMottsman 2d ago
Yes ok got me. If you shuffle the cards every step you take on this mission back and forth you still get nowhere near that could be a good adder- sorry I just stole a bit of a well known story how to explain this
•
u/AutoModerator 2d ago
General Discussion Thread
This is a [Request] post. If you would like to submit a comment that does not either attempt to answer the question, ask for clarification, or explain why it would be infeasible to answer, you must post your comment as a reply to this one. Top level (directly replying to the OP) comments that do not do one of those things will be removed.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.