Wikipedia:Reference desk/Archives/Mathematics/2020 May 5

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 5

Probability of duplication, when shuffling a deck of cards

I saw this claim on the internet: Every time you shuffle a deck of cards, chances are you have put them in an order never seen in history. My first reaction was: "that can't possibly be true". Then, it got me wondering. Is that true? Thanks. Joseph A. Spadaro (talk) 04:33, 5 May 2020 (UTC)

There are 52! different orderings, which is approximately $8*10^{67}$. Meanwhile, the estimated number of humans who have ever lived is about $10^{11}$, and 80 years is about $2.5*10^{9}$ seconds. So if every person in history shuffled a deck of cards every second of their lives, and they always got a configuration that had never been seen before, that would be somewhere around $2.5*10^{20}$ configurations, which is a minuscule fraction of $8*10^{67}$. So if we assume that shuffling gives a uniform distribution on the orderings, then yes, the claim is overwhelmingly true. Now, this isn't that great an assumption, but I'm not equipped to say how much it affects things. My intuition is that it's still a fair claim.--163.47.115.72 (talk) 05:41, 5 May 2020 (UTC)

However, one observable universe filled with protonic monkeys will shuffle a deck into canonical order in a jiffy. There is a relation with the Birthday paradox. Modelling the set of possible shuffles as the different days of a very long year, and the random shuffles produced by shufflers as having their shuffles as their birthdays, we are considering the probability that in a ginormous room of random shuffles two have the same birthday. If $d$ is the number of days in the year (here approximately $8{\cdot }10^{67}$), the number of random shuffles in the room needed to have a fifty-fifty chance of a duplicate birthday is about ${\sqrt {2d\ln 2}}\approx 1.17741{\sqrt {d}}$. For the shuffle birthday calendar, that comes out as less than $1.06{\cdot }10^{34}$. While minute compared to the number $8{\cdot }10^{67}$, it is still impossibly large. Dividing it by the current estimate of the number of seconds since the Big Bang, about $4.36{\cdot }10^{17}$, we see that an average number of more than 20,000,000,000,000,000 shuffles per second would be needed, for the entire age of the universe, to get the chances up to 50%.  --Lambiam 07:49, 5 May 2020 (UTC)

The following problem is more interesting: Assuming current population levels and two children per family, estimate the time interval for which there is a 50% chance that a mother of a child gives birth to a twin sibling of the child she already has. Count Iblis (talk) 10:28, 5 May 2020 (UTC)

Hmmm. I don't understand what you're asking. You said: there is a 50% chance that a mother of a child gives birth to a twin sibling of the child she already has. Is that the same exact question (or is it a totally different question) than asking about: there is a 50% chance that a pregnant woman has twins at all? I don't "follow" your wording. Does the lady already have a first baby; and then gives birth to twins (baby #2 and baby #3)? Or does the lady have one baby (baby #1) and -- a few minutes later -- baby #2, the twin to baby #1, comes out? Thanks. Joseph A. Spadaro (talk) 14:32, 5 May 2020 (UTC)

She has a baby and a few years later she becomes pregnant again and gives birth to another baby. What is the probability that the two children are genetic twins? Count Iblis (talk) 16:08, 5 May 2020 (UTC)

If you merely look at the first 10 cards then there are 52!/42! = 57,407,703,889,536,000 possibilities, around 57 million billion. If it's random then that's already plenty to probably never have occurred in human history when the actual number of shuffles is considered. PrimeHunter (talk) 11:39, 5 May 2020 (UTC)

Maybe I am misinterpreting the question. I was not (necessarily) thinking of human beings doing the shuffling. I was picturing, say, some huge casino --- or maybe hundreds of huge casinos --- where a computer or some mechanized machine performs thousands/millions of shuffles per day. Isn't the "number of shuffles ever performed throughout history" ( which -- I believe -- is the denominator? ) relevant? Granted, computers and automated systems are a relatively modern invention. But, theoretically, can't many automated machines that keep working all day, every day, eventually get a repeated order pattern of cards? And, for some reason, I am thinking of the infinite monkeys typing Shakespeare scenario. Is that even relevant here? Thanks. Joseph A. Spadaro (talk) 14:17, 5 May 2020 (UTC)

• The claim was not that it's impossible to "eventually" get a repeated order". The claim was that "chances are" that the order has not previously occurred. And it refers to that has happened in human history, not to the possibility of constructing machines for the purpose. --76.71.5.208 (talk) 21:04, 5 May 2020 (UTC)

Right. The original statement did not say it's "impossible". It offered a very vague "well, chances are ...". So, that vague and ambiguous phrase can mean anything at all ... from "chances" of 0% to "chances" of 100%. I guess a liberal -- or reasonable -- construction of the phrase is that it means "likely" or "probable" or "50% chance or better". Also, human history contains many events ... including the invention of automated casino machines that shuffle cards ... and were specifically designed to do just that ... no? Why are they "excluded" from "human history"? Joseph A. Spadaro (talk) 04:35, 6 May 2020 (UTC)

Casinos' shuffling machines were not "specifically designed" to keep shuffling cars until a repetition occurred, but to shuffle enough cards to allow games to be played at the desired rate. There is no need to exclude them from history, but there is also no need to include them in hypothetical future scenarios. --76.71.5.208 (talk) 02:36, 7 May 2020 (UTC)

Casino shuffling machines were "specifically designed" to shuffle cards ... for whatever purpose. I am sure that one can use them to allow games to be played at a desired rate in the casino. And, I am sure they can be put to many other uses (e.g., similar to the 1950's research at Bell Labs to test scientific hypotheses about shuffling). Also, at last check, the year 1955 was in the past (i.e., a portion of "human history"). Research done in 1955 does not represent a "hypothetical future scenario". In fact, quite the opposite ... for both "hypothetical" and "future scenario". Joseph A. Spadaro (talk) 03:34, 7 May 2020 (UTC)

"But, theoretically, can't many automated machines that keep working all day, every day, eventually get a repeated order pattern of cards?". Sure; they might even get the same shuffle twice in a row. It's just very unlikely. As has already been noted, the answer depends on whether you interpret the problem to mean that any one specific shuffle has been seen before, or if there have ever been any two shuffles that have been the same. Even in the latter case, as Lambiam noted, the chances are minuscule. –Deacon Vorbis (carbon • videos) 15:53, 5 May 2020 (UTC)

Thanks. So, interpretation #1 = that any one specific shuffle has been seen before. And, interpretation #2 = if there have ever been any two shuffles that have been the same. How are those two thing different? Are they not the same? Or, is the distinction: the probability of a second specific shuffle, given that we know we already had the first specific shuffle? Joseph A. Spadaro (talk) 16:35, 5 May 2020 (UTC)

Imagine you throw a die 4 times and the last time it comes up six. Odds of #1: you haven't thrown two sixes during the four throws: (5*5*5)/(6*6*6). Odds of #2: you haven't thrown two same numbers during the four throws: (5*4*3)/(6*6*6). 89.172.88.15 (talk) 19:26, 5 May 2020 (UTC)

I am no expert at this stuff, but your example seems completely different. When you roll a die, you get "one" result (say, you roll a "6") ... and the "other" five results do not occur (the 1, 2, 3, 4, and 5). When you shuffle a deck, you always have to use all 52 cards, each and every time. I assume this is a significant difference in the examples of the shuffles versus rolling a die. But, I have no idea. Joseph A. Spadaro (talk) 04:48, 6 May 2020 (UTC)

Shuffling is like rolling a 52!-sided die. From a mathematical point of view, there is no essential difference.  --Lambiam 19:19, 7 May 2020 (UTC)

OK. Thanks. Gotcha. Joseph A. Spadaro (talk) 19:48, 8 May 2020 (UTC)

To answer your infinite monkey question: yeah, but why would they? It is doubtful that humanity has done much more than say 10^15 shuffles while playing card games over the course of last few centuries since the 52-card deck was invented. As for not playing card games. A bunch of computers dedicated solely to shuffling cards can probably beat that but I doubt even they could come close to the 10^67 number during the current lifetime of the universe, even if someone would fund such nonsense.

However many people are piss poor at shuffling cards. If someone only does a rudimentary overhand shuffle (or the cards aren't shuffled at all, as three card brag requires for example) the probability of getting the same deck twice in a playing session probably increases noticeably. I think it's likely that decks have been repeated numerous times throughout the human history in poorly shuffled playing sessions. 89.172.88.15 (talk) 19:26, 5 May 2020 (UTC)

I assume that the original question was referring to a "good shuffle" or a "truly" random shuffle. Not a poor shuffle or no shuffle at all. Joseph A. Spadaro (talk) 04:44, 6 May 2020 (UTC)

Also, apparently, someone did indeed fund "such nonsense". The shuffling article -- pointed out by an editor below -- discusses some research in the 1950's at Bell Labs. Joseph A. Spadaro (talk) 04:59, 6 May 2020 (UTC)

I showed above that you need 10³⁴ random shuffles before you have a 50–50 chance of a repetition. That is independent of whether the shufflers are a handful of humans or a planetful of ultrahigh-speed shuffling machines. How fast do you think these can shuffle, and how many can be built before they form a black hole?  --Lambiam 19:44, 5 May 2020 (UTC)

That was exactly my point, as I asked above. Doesn't the "denominator" (somehow) matter? To me, the denominator represents "all of the shuffles that have ever been performed throughout human history". (I think?) So, a few people manually shuffling a few cards, here and there, is one thing. But, automated casino machines -- that perform millions of shuffles per day -- is another thing. I assumed that that affected the denominator, and thus, affected the general probability. (I could be wrong?) So, I thought that "the total number of shuffles ever performed throughout history" was somehow relevant to the analysis. Joseph A. Spadaro (talk) 04:54, 6 May 2020 (UTC)

It is, but even if you think that every order historically produced by a shuffle has been "seen", the number of shuffles that could have been produced, even in the best of circumstances, is incredibly minute compared to the totality of possible outcomes, which are far more numerous than there are molecules of water in all the oceans, even more than there are atoms in the solar system.  --Lambiam 13:33, 6 May 2020 (UTC)

Yes, thanks. I guess it's all semantics, in the end. We are either talking about a "really big number" ... versus a "really, really, really big number". I guess. I am not sure at which point the difference (as to how "big" the number is) becomes "significant". Thanks. Joseph A. Spadaro (talk) 16:18, 6 May 2020 (UTC)

There are two different numbers: a) there are N=52!=8e67 different shuffles. Also, there are about 3e7 seconds in a year. So if you set up shuffling machines to do 1 billion shuffles per second for 1 billion years, that is about 3e25 total shuffles. Therefore: if you shuffle the cards right now after that, your chances of getting a shuffle that has already been seen is about 3e25/8e67 = 4e-43, infinitesimally small. Also: b) if there have been K=3e25 shuffles (call them s1,s2,s3...) done in the past, each shuffle has the potential to have been a duplicate of some other. There are K**2/2 = 4.5e50 such pairs, so the likelihood of some shuffle having occurred twice is about 4.5e50/8e67=5.6e-18 or 1 in 2e17. That's still awfully small but it's more physically comprehensible. E.g. I read somewhere that around 1e30 bacteria currently live on Earth, so we're not talking about cosmic magnitudes any longer. 2602:24A:DE47:B270:DDD2:63E0:FE3B:596C (talk) 23:25, 7 May 2020 (UTC)

Given: a discrete random variable with $N$ equally likely different possible values, and a sequence of $S$ independent outcomes $x_{1},...,x_{S}$. If a next outcome $x_{S+1}$ is obtained, what is the probably it has not occurred before? Since all those outcomes were independent, it is the product of $\mathrm {P} (x_{S+1}\neq x_{i})$ for $i=1,...,S$, which equals $\left({\tfrac {N-1}{N}}\right)^{S}=e^{-\lambda S}$, where $\lambda =\ln {\tfrac {N}{N-1}}\approx {\tfrac {1}{N}}$ for large $N$. To get this probability below ${\tfrac {1}{2}}$, we need $S>\lambda ^{{-}1}\ln 2\approx 0.69315N$.  --Lambiam 07:13, 8 May 2020 (UTC)

@Lambiam: Thanks. Wow, I didn't understand a word of that. But, you seem to have a good "handle" on this question / issue. Let me re-phrase the question, if I may. Let's say that a certain specific shuffle occurs right at this moment. Now, we want to look for the next time that we'd expect this same exact / specific shuffle to happen again. When would we expect that to occur? I am looking for an answer in this format (if possible). If the specific shuffle occurs today, the next time that we'd expect to see that same shuffle again is __________ years from now. It may be millions or billions of years. But, that would help me to understand (and contextualize) these large numbers a bit more. Thanks. Joseph A. Spadaro (talk) 19:56, 8 May 2020 (UTC)

See Shuffling, specifically the section on randomization. --RDBury (talk) 19:49, 5 May 2020 (UTC)

Thanks, all. Joseph A. Spadaro (talk) 17:23, 12 May 2020 (UTC)