Introduction to Probability · Problem 3.1.19

Combinatorics — Grinstead & Snell

Mathematics — Probability · permutations

Problem

Suppose that on planet Zorg a year has

n

days, and that the lifeforms there are equally likely to have hatched on any day of the year. We would like to estimate

d

, which is the minimum number of lifeforms needed so that the probability of at least two sharing a birthday exceeds

1/2

. (a) In Example 3.3, it was shown that in a set of

d

lifeforms, the probability that no two life forms share a birthday is

\frac{(n)_d}{n^d},

where

(n)_d = (n)(n-1)\cdots(n-d+1)

. Thus, we would like to set this equal to

1/2

and solve for

d

. (b) Using Stirling's Formula, show that

\frac{(n)_d}{n^d} \sim \left(1 + \frac{d}{n-d}\right)^{n-d+1/2} e^{-d}.

x

, we have

\log(1+x) \sim x - \frac{x^2}{2}.

(We are implicitly using the fact that

d

is of smaller order of magnitude than

n

. We will also use this fact in part (d).) (d) Set the expression found in part (c) equal to

-\log(2)

, and solve for

d

as a function of

n

, thereby showing that

d \sim \sqrt{2(\log 2)\, n}.

Hint: If all three summands in the expression found in part (b) are used, one obtains a cubic equation in

d

. If the smallest of the three terms is thrown away, one obtains a quadratic equation in

d

. (e) Use a computer to calculate the exact values of

d

for various values of

n

. Compare these values with the approximate values obtained by using the answer to part (d).