1
$\begingroup$

I badly misread this problem:

You just won 2016 socks. Some of them are white, some are blue. The color of each sock was randomly chosen, with a 50/50 probability. Is it more probable that the socks can be paired, or that you will remain with two unmatching socks?

The correct answer is 50%, but I just woke up so I had this chain of thought:

That cannot be right. It's possible that all the socks might be blue, or all white, and then you cannot pair up any of them.

After my coffee, I realized that a "pair" is two socks of the same color, not, as my sleep-addled mind had insisted, one blue and one white.

But imagine, you are an eccentric who always wears one blue sock and one white. Now what are the odds of "pairability"?

For a more realistic example, consider a club at which men want to dance with women and vice-versa. The doorman admits the first 2016 people, without regard to who has already been admitted. Given that people show up randomly but in exactly equal proportions, What are the odds that exactly 1008 men and 1008 women are admitted?

(I am still pretty sleepy so my first instinct was to post on workplace.stackexchange.com for advice about hiring a better doorman. Then I came up with a solution that (a) isn't very good and (b) might not even be correct, given that 10 minutes ago, I was too sleepy to remember that socks are supposed be the same color. I will post it as an answer below, but feel free to critique or correct it.)

$\endgroup$
1
  • $\begingroup$ I'm about to go to bed and I just misread the socks problem the same way you did! $\endgroup$
    – Oliphaunt
    Jun 5, 2016 at 19:39

3 Answers 3

5
$\begingroup$

Following on from Malvolio's answer (I imagine him crying "A plague on both your genders!"), Stirling's approximation to $n!$ is

$n! \approx \dfrac{\sqrt{2\pi n}\;n^n}{e^n}$.

Write n for 1008. Then the chance is \begin{array}{rcl} \dfrac{(2n)!}{2^{2n}n!^2} & \approx & \dfrac{\left[ \dfrac{ \sqrt{4\pi n}(2n)^{2n} } { e^{2n} }\right] } {\left[ \dfrac{ 2^{2n}(2\pi n)n^{2n} } { e^{2n} } \right] } \\ & \approx & \dfrac{ \sqrt{4\pi n}(2n)^{2n} } { 2^{2n}(2\pi n)n^{2n} } \\ & \approx & \frac{\sqrt{4\pi n}}{2\pi n}\\ & \approx & \frac{\sqrt{\pi n}}{\pi n}\\ & \approx & \frac1{\sqrt{\pi n}} \end{array}

To anyone wondering how come Malvolio and I end up with different formulas: my $n$ has half the value of Malvolio's $n$.

$\endgroup$
2
$\begingroup$

Do it combinatorially:

There are $2^{2016}$ possible strings of Ms and Fs 2016 long. Of them, 2016-choose-1008 have exactly 1008 Ms. So the chances are $2^{2016} / ( 2016! / 1008!^2 )$ to 1, against.

As I say, this is not a good solution, even if correct, because it is difficult to actually calculate, so I am open to improvements.

$\endgroup$
5
  • $\begingroup$ The actual probability is 1.7768%. However, you can use Stirling's approximation to approximate the factorials, giving a probability of $\sqrt{\frac{2}{\pi n}}$. In this case the approximation gives 1.7770%. $\endgroup$ Jun 5, 2016 at 19:59
  • 1
    $\begingroup$ Another method of obtaining the same result is approximating the binomial distribution $B(n,\frac{1}{2})$ as a normal distribution ${\mathcal N}(n\cdot\frac{1}{2},\sqrt{n\cdot\frac{1}{2}\cdot\frac{1}{2}})$. The PDF of the normal distribution at it's peak is just $\frac{1}{\sqrt{2\pi}\sigma}$, so the probability is $\left(\sqrt{2\pi}\sqrt{\frac{n}{4}}\right)^{-1}=\left(\sqrt{\frac{\pi n}{2}}\right)^{-1}$, the same as before. $\endgroup$ Jun 5, 2016 at 20:12
  • $\begingroup$ @2012rcampion -- 1.7768%? That's at least an order of magnitude greater than I would have guessed. $\endgroup$ Jun 5, 2016 at 22:48
  • $\begingroup$ It makes sense when you consider that the standard deviation of the number of same-colored socks is $\sqrt{np(1-p)}=\sqrt{2016/4}\approx 22$. This means that "most" of the probability is concentrated in about the middle 50 numbers, so a probability of 2% seems reasonable. (Side note: If you want to do calculations with large numbers, I recommend wolfram alpha.) $\endgroup$ Jun 5, 2016 at 23:39
  • $\begingroup$ I can use bc to compute a precise rational axpression for the answer but it has more digits than I can fit in a comment $\endgroup$
    – Jasen
    Jun 6, 2016 at 1:31
1
$\begingroup$

We can generalize this to any number of genders. Imagine a species with $g$ genders, and $ng$ of them. What's the probability that we have equal numbers of each, so that they can form $n$ perfect $g$-tuples? Answer: $g^{-gn}\binom{gn}{n;n;\ldots;n}$ where the thing on the right is a multinomial coefficient. That equals $g^{-gn}\frac{(gn)!}{n!^g}$, which by Stirling is approximately $g^{-gn}\frac{\sqrt{2\pi gn}\left(\frac{gn}{e}\right)^{gn}}{\left(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right)^g}$. Cancelling things that cancel, this becomes $\sqrt{\frac{g\phantom{1}}{(2\pi n)^{g-1}}}$. Sanity check: when $g=1$ this is 1, and when $g=2$ it matches the answer already given. Note that it requires that $n$ be not only large but large in comparison to $g$.

$\endgroup$
1
  • $\begingroup$ Well, if the number of people at the club isn't large compared to the number of genders at the club, it's less "going to a club" and more "getting a room". $\endgroup$ Jun 6, 2016 at 18:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.