# In n choose k, how many would you first skip over, on average?

Let's suppose I have n playing cards and I need to find k specific ones by going through them one by one. It does not matter what order I find the cards in, but any of the k cards could be anywhere in the deck. What is the average number of cards, that would I be expected to discard before finding the very first card I wanted? I can see the trivial cases where if I knew that all of the cards that I needed were together at the bottom of the deck, I would have to discard n-k, and if just the first card I needed were at the top, I would discard 0 before getting to it. However, I can't generally assume that I know where the cards are going to be, so these special cases aren't particularly helpful except as examples of the upper and lower bounds. It seems to me that if k were 1, then the average number of cards to skip would be n/2, but I don't know how to calculate for a general k where n $\ge$ k $\ge$ 0.

I know how to calculate the number of total possibilities in n choose k, but I can't figure out how to tell what the average number of skipped entries would be for finding just the first one.

Problems of expectation are often quite easy to solve due to linearity of expectation, which applies even when random variables are not independent.

There are k specified cards, and (n-k) "others".
Let X(i) be an indicator random variable that assumes a value of $1$ if the $i^{th}$ "other" card is ahead of the first specified card, and $0$ otherwise.

Consider the $i^{th}$ "other" card in conjunction with the k specified ones.
Since each "other" card is equally likely to be drawn before the first specified card,
$P(i^{th}\; "other"\; card\; is\; drawn\; before\; the\; first\; specified\; card) = \dfrac1{k+1}$

Now the expectation of an indicator random variable is just the probability of the event it indicates, so $E(X_i) = \dfrac1{k+1}$

And by linearity of expectation, we have $E\Sigma (X_i) = \Sigma E( X_i) = \dfrac{n-k}{k+1}$

The distribution of your random variable is a negative hypergeometric distribution, where we set the number of wanted cards (before to stop counting unwanted drawn cards) to $1$.

If $N$ is the total number of cards, $K$ is the total number of wanted cards and $r$ is the number of wanted cards we count before to stop drawing cards then the expected number of unwanted drawn cards is

$$r\frac{N-K}{K+1}$$

• how do you deal with the prob of success not being constant? – futurebird Jul 1 '17 at 17:18
• @future I just copied the results of this distribution. The details are in the link. – Masacroso Jul 1 '17 at 17:19
• in other words how would the problem change if our deck were infinite in size with the cards we want distributed evenly with k/52 prob. – futurebird Jul 1 '17 at 17:20
• @future in this case this will be a negative binomial distribution – Masacroso Jul 1 '17 at 17:22
• ok I thought that was what you were talking about I didn't know this had a name. – futurebird Jul 1 '17 at 17:23

What is the probability that you draw m cards and and get the ones you want?

There are $\frac{m!}{k!(m-k)!}$ ways to arrange k successes and m-k failures.

The probabilty of drawing the k desired cards in a row is:

$\frac{k\cdot(k-1)\cdot(k-2)\cdots1}{52\cdot51\cdot50\cdots(52-k+1)}$

The probabilty of drawing the m-k not desired cards after that is:

$\frac{(52-k)\cdot(52-k-1)\cdot(52-k-2)\cdots(52-k-(m-k)+1)}{(52-k)\cdot(52-k-1)\cdot(52-k-2)\cdots(52-k-(m-k)+1)}=1$

Put it together and we have

$\frac{m!}{k!(m-k)!}\frac{k!(52-k)!}{52!}=\frac{m!(52-k)!}{(m-k)!52!}$

Now we can treat this like a discrete probability of a random variable X with pmf $P(m)=\frac{m!(52-k)!}{(m-k)!52!}$

This is the probability of getting k cards after drawing m cards. Now we multiply m the number of card it takes to have all k desired cards by the probability of it taking that many cards and take the sum.

Then $E[X]=\sum_{m=k}^{52}m\frac{m!(52-k)!}{(m-k)!52!}$ This is the expected value of the hypergeometric distribution.