The Birthday Problem

 

The Proof  

We will show that the coincidence, suspected by the author to have no mathematical significance, was not a coincidence at all.

Given: 

 n, the number of days in a year, e.g.,  n= 365;
 k, the number of partygoers needed for the probability of two identical birthdays to exceed  1 - p, e.g.,  k= 23  for  p= .5;
 b, the number of different pairings of  k people, that is, b=(k(k-1)/2, e.g., b= 253  for  k= 23;
 c, the number of partygoers needed for the probability of one of them having  your birthday to exceed  1 - p, e.g.,  c= 253  for  n= 365  and  p= .5;

and these well-known approximations:

 [A] 
      if a<< n
 [B] 
   if i<< j

we will show that:


is not a coincidence, but is true for all reasonable values of  n and  p.


 Substitute 
into [A] 
yielding:
[C] 

 Multiply both sides by n
[D] 

 Raise both sides to the power k
[E] 

 Simplify the double exponent
[F] 

 Substitute b for 

[G] 

 On the left side, combine the powers of n
[H] 

[I] 

[J] 

 Substitute j = n- 2 , i = k- 2  into  [B] 

[K] 

[L] 

 The right sides of [J] and [L] are equal; pair the left sides
[M]

 Multiply both sides by n-1
[N] 

 Multiply both sides by n
[O] 

[P] 

 Divide both sides by 

[Q] 

[R] 

 Substitute p for 

[S] 

[T] 

 Substitute c for 

[U]

 QED.

I have not bounded the error analytically, but empirically, I have shown the error in:


to be within 1.0 when n> 4 and p> .04.