(Introduction to Probability, Blitzstein and Nwang)
Recall de Montmort’s matching problem from Chapter 1: in a deck of n cards labeled 1
through n, a match occurs when the number on the card matches the card’s position in
the deck. Let X be the number of matching cards. Is X Binomial? Is X Hypergeometric?
Again stuck at a textbook problem that was probability designed for 2 minutes…
It's clearly not binomial, as the 'draws' are not independent, but I can't see why it should be hypergeometric. As I understand it, the story behind the hypergeomtric was that there is a urn with black and white balls, we take a sample of size n without replacement and count the number of white (or black) balls we see. But where are the black and white ball analogues in the card matching problem?
To get the PMF, I would have guess something like
$$
P(X=k) = \frac{\binom{n}{k} !(n-k)}{n!},
$$
where $n!$ is the number of possible card arrangements, $\binom{n}{k}$ the number of possibilities to have $k$ matching cards out of $n$ and the subfactorial $!(n-k)$ the number of possibilities to derange the remaining cards such that there is no additional match.
- What is the 'Hypergeometric story' behind the card matching problem?
- How to derive the hypergeometric distribution from the problem?
Best Answer
I guess the correct answer is "neither".
Blitzstein discusses the case P(X=1). The general answer P(X=k) is given here https://probabilityandstats.wordpress.com/2010/05/02/more-about-the-matching-problem/
\begin{aligned}P(X_n=k)&=\displaystyle \binom{n}{k}\displaystyle \biggl(\sum \limits_{i=0}^{n-k} (-1)^{i} \frac{(n-k)!}{i!}\biggr) \frac{1}{n!}\\&=\frac{1}{k!}\sum \limits_{i=0}^{n-k} \frac{(-1)^{i}}{i!}\end{aligned}