# Birthday paradox: Comparing the original version with the same-birthday-as-you version

The birthday paradox itself is well known. I am only interested in a small aspect here:

The number of pairings in the original problem is

$${23 \choose 2} = \frac{23 \cdot 22}{2}=253$$

Another version is the same-birthday-as-you problem. It turns out that you need also at least $253$ people to get over $50%$ probability.

$$1 - \left( \frac{364}{365} \right)^{253}=1-0.499$$

I am interesting in this double occurrence of $253$:

My question
Who is right and why?

Just for the sake of completeness after receiving the great answers below (for which I am very grateful): In the meantime I had also contacted Ian Stewart on the matter and he too acknowledges the connection. He told me that in fact one of his readers wrote in soon after the article was published to point it out.

-
Well, given the second result, the number $23$ should be seen as the least integer $n$ satisfying ${n \choose 2} \geq 253$. I think that the fact that the least such number ($23$) actually attains this bound is a coincidence, but I'm not sure. (What would happen if a year has $366$ or $367$ days?) – TMM Mar 12 '13 at 13:14

The first problem: $23$ comes as the answer to "the smallest integer $n$ such that $n!\binom{365}{n} / {365^n} < \frac12$". Then the $253$ comes as $\binom{23}{2}$.
The second problem: $253$ comes as the answer to "the smallest integer $m$ such that $\left(\frac{364}{365}\right)^m < \frac12$."

So the first $253$ is necessarily a number of the form $\binom{n}{2}$ (a triangular number), while the second $253$ can be any integer whatsoever. In that sense, it is a coincidence that they happen to be exactly equal (that the answer to the second problem happens to be a triangular number).

On the other hand, it is not a coincidence that they are approximately equal. We can see this by approximating the first problem (the classical birthday problem) as follows. If there are $n$ people, there are $\binom{n}{2}$ pairs. For a given pair, the probability that they don't have their birthday in common is $\frac{364}{365}$. If we treat all these $\binom{n}{2}$ pairs as independent (this is the approximation) then the probability that all birthdays are distinct is simply got by multiplying $\frac{364}{365}$ those many times, thus we want the smallest $n$ such that $\left(\frac{364}{365}\right)^{\binom{n}{2}} < \frac12$. Equivalently, $253$ is the answer to "the smallest $\binom{n}{2}$ such that $\left(\frac{364}{365}\right)^{\binom{n}{2}} < \frac12$." This is an approximation to the exact problem, but not a very far off one.

Conclusion: Ian Stewart more or less makes a mistake, when he writes

"Incidentally, the fact that this answer to the second problem is the same as the number of pairings in the first problem (253 pairings for 23 people) seems not to have any mathematical significance. In fact, it seems to be a coincidence."

It is not at all a coincidence that the answer to "(approximately) the smallest $\binom{n}{2}$ such that $\left(\frac{364}{365}\right)^{\binom{n}{2}} < \frac12$", and the answer to "the smallest integer $m$ such that $\left(\frac{364}{365}\right)^m < \frac12$" happen to be approximately equal.

For concreteness, here for various values $d$ in place of $365$ are the actual values $\binom{n}{2}$ (where $n = n(d)$ is the answer to the first problem) and $m$ (where $m = m(d)$ is the answer to the second problem). Note that around $d = 365$ the second column $\binom{n}{2}$ varies slowly, being sometimes less and sometimes more than the third column $m$, because it can only take values like $\binom{22}{2} = 231$, $\binom{23}{2} = 253$, $\binom{24}{2} = 276$, etc., while the third column can also take values in between.

$$\begin{array}{r|r|r} d & \binom{n}{2} & m \\ \hline 50 & 36 & 35 \\ 100 & 78 & 69 \\ 200 & 136 & 139 \\ 250 & 171 & 173 \\ 300 & 210 & 208 \\ 330 & 231 & 229 \\ 340 & 231 & 236 \\ 350 & 253 & 243 \\ 360 & 253 & 250 \\ 363 & 253 & 252 \\ 364 & 253 & 252 \\ \hline 365 & 253 & 253 \\ \hline 366 & 253 & 254 \\ 367 & 253 & 255 \\ 370 & 253 & 257 \\ 380 & 276 & 264 \\ 390 & 276 & 270 \\ 400 & 276 & 277 \\ 500 & 351 & 347 \\ 600 & 435 & 416 \\ 800 & 561 & 555 \\ 1000 & 703 & 693 \\ 2000 & 1378 & 1386 \\ 5000 & 3486 & 3466 \\ 10000 & 7021 & 6932 \\ 20000 & 13861 & 13863 \\ 50000 & 34716 & 34658 \\ 100000 & 69378 & 69315 \end{array}$$

Values of $d$ upto $1000$ for which the two numbers coincide (like they do with $d = 365$) are many: 4, 8, 9, 14, 21, 22, 30, 40, 51, 52, 64, 65, 79, 95, 112, 113, 131, 151, 173, 196, 220, 221, 246, 247, 274, 303, 333, 365, 398, 432, 433, 468, 469, 506, 545, 585, 586, 627, 628, 670, 671, 715, 716, 761, 762, 809, 858, 908, 909, 960, 961. These are also precisely the values of $d$ for which $m$ happens to be a triangular number. Actually, it can be proved with some effort using the known bounds on $n$ that this is always true in general.

-

I would say it is a coincidence that they are exactly equal, but not that they are close. The second $253$ can be any natural you want, but the number of pairings are limited to triangular numbers, which have significant gaps. The two calculations differ slightly because the first can have multiple pairs or triples, while the second cannot, but this is a small effect. Ignoring that, in both cases we are looking for the smallest available $n$ such that $\left(\frac{364}{365}\right)^n \lt \frac 12$

-
Thank you for your answer. I agree both are similar, yet in the case of the original paradox the falling factorial power in the numerator is growing considerable slower than $364$ to the $n$ in the other version. This is why you need $23$ in one case and $253$ in the other after all. – vonjd Mar 12 '13 at 13:34
@vonjd: but you still need the same number of potential pairs. It is just you get pairs quadratically in the first case and linearly in the second. – Ross Millikan Mar 12 '13 at 13:37
Ok, I begin to see the idea. I think this comment is rather helpful, perhaps you want to include it into your original answer. Thank you again. – vonjd Mar 12 '13 at 13:39
+1, I essentially elaborated on this in my answer. – ShreevatsaR Mar 12 '13 at 17:44