People are arriving at a party one at a time. While waiting for more people to arrive they entertain themselves by comparing their birthdays. Let X be the number of people needed to obtain a birthday match, i.e., before person X arrives there are no two people with the same birthday, but when person X arrives there is a match. Find the PMF of X. (Introduction to Probability, Blitzstein and Hwang, p.128)

The CDF is $P(X\leq k) = 1 - \frac{\binom{365}{k}k!}{365^k}$, so the PMF can be obtained by:

\begin{align} \\ P(X=k) &= P(X\leq k) - P(X\leq k-1)\\\\ &= \left( 1 - \frac{\binom{365}{k}k!}{365^k} \right) - \left( 1 - \frac{\binom{365}{k-1}(k-1)!}{365^{k-1}} \right) \\\\ &= \frac{(k-1)}{365^k} \binom{365}{k-1} (k-1)! \\\\ &=(k-1)*\left(1-P(X \leq k-1 \right)) \\\\ &= (k-1) * P(X > k-1) \end{align}

Is this correct? How do you interpret the results? How to arrive at the PMF without using the CDF?


1 Answer 1


There is an easier way, which lead to the correct answer.

You want $P(k)$, the probability that the first match occurs at person $k$. For that to happen, the previous $k-1$ people must have no matches, and $X$ must match one of them.

The probability of $k-1$ people to have no matches is $$ \frac{N}{N} \frac{N-1}{N} \frac{N-2}{N} \cdots \frac{N-k+2}{N} = \frac{N!}{(N-k+1)! N^{k-1}} $$ with $N = 365$. Then the probability of a match on the k-th person is $$ P(k) = \frac{N!}{(N-k+1)! N^{k-1}} \frac{k-1}{N} = (k-1) \frac{N!}{(N-k+1)! N^{k}} $$

The expression you give is equivalent to $(k-1) \frac{N!}{(N-k+1)! N^{k}}$. But this derivation did not use the CDF.

  • $\begingroup$ This makes sense, but is there a way to immediately see that $P(X=k) = (k-1) P(X \geq k)$ is true? $\endgroup$ Dec 11, 2014 at 22:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .