This notebook is a copy of https://nbviewer.jupyter.org/github/norvig/pytudes/blob/master/ipynb/Socks.ipynb by Peter Norvig. I am only rerunning it, not making any changes this time, since my main purpose here and now is to test the Deepnote integration workflows, as suggested by the Deepnote links in the README file of his repo.
Bram Cohen posed a problem that I'll restate thusly:
You have N pairs of socks, all different, in the dryer. You pull random socks out one-by-one, placing each sock in one of C possible places on the countertop. If the latest sock pairs with another on the countertop, you put the pair away in a drawer. We can ask: 1. What's the probability that you will pair up all 2N socks before you run out of the C places? 2. For a given N, what is the minimum C to have a 50% chance? 3. A 100% chance?
The third question is easy to solve analytically: to be 100% certain of pairing up N pairs, we would need N + 1 countertop spaces, because it is possible that the first N socks are all different, but the next one will always pair with one of the others. How about the other questions?
- Can I come up with a mathematical formula? No.
- Could I calculate an exact answer? Only for small N. Enumerating all permutations of socks would take O((2N)!), but since I don't care which sock is next, only whether it is a match/non-match, I could get that down to O(2(2N)), but that's still bad.
- Could I do a simulation? Yes. And since we're mostly interested in events with probability around 50%, a simulation with, say, 1000 trials is likely to give very good approximations. If we were investigating events with probability 0.0001, we'd need many more trials.
Sock Pairing Simulation
First, we can use
minimum_C to find the countertop size necessary to give a 50% chance of pairing up all the socks, for various values of N. We see that the relation is very nearly linear, and the slope is a little more than 1/2:
Now, for various numbers of pairs of socks N, plot the probability
P(N, C) of being able to pair up all the socks:
I said that I could calculate the probability exactly for small values of N. Let's do that.
Pexact will call
pair_socks once for each posssible permutation of the socks, and will use
fractions.Fraction to get an exact rational number as the probability. This gives us a precise answer, and serves as a check on the inexact function
We see that the
P estimate with 1000 trials is not too bad, and with 10,000 trials it is much better.