When I was in college, the most demoralizing rejection imaginable from a girl was, “I can’t go out with you Saturday night because I have to arrange my sock drawer.”
I have never arranged my sock drawer.
My wife buys socks for me. In fact, I now have three brands of white socks. The dim morning light makes all those socks look the same. Therefore, each morning I must reach into my sock drawer several times before I have a matching pair.
Over the years, this process has become increasingly unbearable to me, so I decided to do something about it.
No, I did not start arranging my socks.
I wrote a computer program that predicted how many socks on average I would have to randomly pick from my sock drawer before some combination of socks in my hands made a matching pair. The program repeated the process 200 times to give me a statistical probability.
The program generated the above figure, which predicted that over 200 days of trying to find a matching pair of socks from my sock drawer,
for 63 of the days, I would find a pair after retrieving 2 socks from my drawer
for 94 of the days, I would find a pair after retrieving 3 socks from my drawer
for 43 of the days, I would find a pair after retrieving 4 socks from my drawer
This means the most likely number of tries to find a matching pair of socks is 3.
Why wouldn’t 2, 3, and 4 tries have the same probability? They're all random outcomes, right?
I decided to enhance my computer program to simulate a drawer full of 35 brands of white socks to give me a better picture of what is going on. Imagine having 35 unsorted brands of white socks in one drawer!
Question: What is the average number of socks selected from 35 brands that will result in a matching pair? I would have thought the answer would be 17, or roughly 35 divided by 2.
Answer: Instead of 17 socks, only 7 socks on average must be selected from the drawer of 35 brands to form a matching pair.
Notice there are only a few cases where more than 17 tries are needed to find a pair, and that is only halfway to 35.
The graph above is consistent with my first graph of three sock brands. Both graphs show “front-loaded” results, meaning the likelihood of finding a pair is sooner than later. This is good news if you’re trying to find matching socks in the early morning.
Then it dawned on me that my sock-drawer problem is mathematically identical to the classic Birthday Problem described in this Wikipedia link: “How many people need to be in a room before it is more likely than not that two people in the room share the same birthday?”
One would think the answer would be about 182 people, or 365 days divided by 2.
But the answer isn't 182. It is 23. Just like my sock-drawer problem, the solution is “front-loaded,” meaning the answer is significantly fewer than one-half of 365.
Let’s return to socks.
The following graph from my program shows (for the case of 35 brands of socks) the probability of finding a pair of socks as a function of the number of selected socks. Clearly, on the first try, the probability is zero because I have only one sock in my hand. And after 36 tries the probability is 100%. But what about in between?
The above graph is telling us that the 50% probability line corresponds with 7 tries. This is consistent with the previous graph, where the biggest "hump" is at seven tries. In other words, “after 7 tries, I am more likely than not to have found a pair of socks.”
Wikipedia provides the following equation for the probability of a pair of things matching within a group, which I then adapted to my sock-drawer problem:
The above equation creates the blue line overlaid onto my program's results shown in the following figure. This confirms that my sock-drawer problem and the Birthday Problem are indeed the same problem except for the number of possibilities of 3 or 35, versus 365.
Shuffling Cards
The statistics of shuffling cards is mathematically similar to predicting common birthdays or finding pairs of socks. It's the same math, just with different numbers.
How many possible shuffle combinations are there for a 52-card deck? The answer is "52 factorial." What does that mean in English? "Fifty-two factorial," symbolized by 52!, is calculated by multiplying the following: 52 * 51 * 50 * 49 * 48 * 47 * ... * 3 * 2 * 1. "Fifty-two factorial" comes out to be 8,066,000 followed by sixty-one more zeros. To help you understand just how big that number is, it is 800 quadrillion times the number of atoms in Earth.
A very large number of card shuffles indeed!
But, how many shuffles would it take to repeat the same shuffle? This is where someone starts shuffling and stops the moment he or she has identically repeated any previous shuffle. This is a much smaller number of shuffles than the total number of possible shuffles. That number of paired shuffles (like finding a pair of socks or finding two people in a room with the same birthday) is well below "fifty-two factorial." That number is only 10,580,000,000,000 followed by 21 zeros. That many atoms would only make a cube of dirt about as tall as a sixteen-story building.
If anyone has told you he or she has come up with the same fifty-two card shuffle twice, that person is lying.
Conclusion
Every morning I should grab three socks at once. This will give me roughly a 75% chance of finding a pair in one shot. But even with this approach, about 1 out of 4 days I will still have to reach into my sock drawer a second time.
Or I could have only one brand of socks.