The Birthday Problem

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]

[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.