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.
 A: 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}$
A: 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}$$
A: 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.
