# Birthday problem: Let X be number of people needed for a match. Find the PMF of X.

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?

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.
• This makes sense, but is there a way to immediately see that $P(X=k) = (k-1) P(X \geq k)$ is true? Dec 11, 2014 at 22:19