# 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.

## 3 Answers

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.