Past exam of the mathematics course of the University of Cambridge / 2009 / ia / Paper 2 / 4F (Probability)

Table of contents
- Solution 4F

Solution

B \cap A_{i}

are pairwise disjoint and their union is

B

. Finite additivity and the definition of conditional probability therefore give the law of total probability:

P (B) = \sum_{i = 1}^{n} P (B \cap A_{i}) = \sum_{i = 1}^{n} P (A_{i}) P (B ∣ A_{i}) .

For the birthday problem, let

D

mean that all birthdays differ. For

n \leq 365

, sequential conditioning on previous distinct birthdays and independence of random variables give

P (D) = \prod_{j = 0}^{n - 1} (1 - \frac{j}{365}) \leq exp (- \sum_{j = 0}^{n - 1} \frac{j}{365}) = exp (- \frac{n ( n - 1 )}{730}) .

Here each factor uses the stated bound

1 - x \leq e^{- x}

. For

n \geq 29

,

n (n - 1) \geq 812 > 730 lo g 3

, so

P (at least one shared birthday) = 1 - P (D) \geq \frac{2}{3} .

For

n > 365

a match is certain by the pigeonhole principle. The threshold from the exponential bound is

(1 + 1 + 2920 lo g 3) /2 \approx 28.8

, so

29

suffices.

 Ancestors (9)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version