(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?
  • 1
    $\begingroup$ The quickest way to the answers might be to consider $P(X=n)$ and $P(X=n-1)$ $\endgroup$ – Henry Dec 13 '14 at 20:22
  • 1
    $\begingroup$ To consider the actual distribution, look at rencontres numbers $\endgroup$ – Henry Dec 13 '14 at 20:24
  • 1
    $\begingroup$ @Henry Thank you for that hint. So I think I got the distribution right. Is the answer that the hypergeometric has nothing to do with the problem? I wouldn't expect this based on the formulation of the exercise. $\endgroup$ – NoBackingDown Dec 13 '14 at 21:06
  • $\begingroup$ I don't think your expression gives the correct answer for $P(X=n)$ and $P(X=n−1)$ or the other $k$ $\endgroup$ – Henry Dec 13 '14 at 23:15
  • 1
    $\begingroup$ @Henry : I don't see what's wrong with it. According to the Wikipedia article, If one divides all the entries in the nth row by n!, one gets the probability distribution of the number of fixed points of a uniformly distributed random permutation of { 1, ..., n }. The probability that the number of fixed points is k is" $\frac{D_{n,k}}{n!}=\frac{\binom{n}{k}*D_{n-k,0}}{n!}$. An explicit formula is $D_{n,m} = \frac{n!}{m!}\sum_{k=0}^{n-m} \frac{-1^k}{k!}$, so $D_{n-k,0} = (n-r)! \sum_{k=0}^{n-r} \frac{-1^k}{k!} = !(n-r)$. Hence, $\frac{D_{n,k}}{n!} = \frac{\binom{n}{k}*!(n-r)}{n!}$ $\endgroup$ – NoBackingDown Dec 14 '14 at 8:31

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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.