Probability of no matches taking $N$ cards out of $rN$ cards at random and matching them against a target deck

120 Views Asked by At

In Feller's introduction to probability the answer to this problem is given by:

$ $$\tag1 p = \sum_{v={2}}^{N} (-1)^{v}{N \choose v}r^{v}{\frac{(rN-v)!}{rN!}}$

Acording to the means of the chapter from which this problem comes from, the probability of at least one of the cards being matched is given by:

$ $$\tag1 P_1 = \sum_{v=1}^{N}(-1)^{v+1}S_v $

Where $S_v$ is the sum of probabilities of the intersection of exactly $v$ cases where there are $v$ matches.

Yet i have some problems with the answer given, because to begin, if you are choosing $N$ cards out of $2N$ at random, should't the factor ${2N \choose N}$ be in the denominator? And also because you are choosing $N$ cards to work with, in the sum, it should't be just $N$ instead $rN$?

1

There are 1 best solutions below

0
On BEST ANSWER

Feller has simplified some intermediate results.

The solution is by application of inclusion/exclusion. We consider all the cards to be distinct, including those that have the same rank, so the $N$ cards out of $rN$ can be selected in $\binom{rN}{N}$ ways and then ordered in $N!$ ways, resulting in $\binom{rN}{N} N!$ possible arrangements, all of which are equally likely.

Using Feller's notation, let $S_{\nu}$ be the probability (with deliberate over-counting) that $\nu$ of the cards in the target deck are matched. We want to count the number of ways that this can happen. The matched ranks can be chosen in $\binom{N}{\nu}$ ways, and each of the $\nu$ ranks can be matched by any of $r$ cards. The remaining cards in the sample of $N$ can be selected in $\binom{rN-\nu}{N-\nu}$ ways, and then ordered in $(N-\nu)!$ ways. So the total number of arrangements is $$\binom{N}{\nu} r^{\nu} \binom{rN-\nu}{N-\nu} (N-\nu)!$$ Therefore $$S_{\nu} = \frac{\binom{N}{\nu} r^{\nu} \binom{rN-\nu}{N-\nu} (N-\nu)!}{\binom{rN}{N} N!}$$ Simplifying, $$\begin{align} S_{\nu} &= \frac{\binom{N}{\nu} r^{\nu} (rN-\nu)! / N!}{(rN)! / N!} \\ &= \frac{\binom{N}{\nu} r^{\nu} (rN-\nu)!}{(rN)!} \end{align}$$ which is Feller's result.

Feller makes one more simplification. The probability of no match is, by inclusion / exclusion, $$P_0 = \sum_{\nu=0}^N (-1)^{\nu} S_{\nu}$$ but $S_0 = S_1$, so the first two terms cancel, and $$P_0 = \sum_{\nu=2}^N (-1)^{\nu} S_{\nu}$$