# Sampling without replacement until hitting a subset

I randomly sample uniformly from $\{1,..,N \}$ without replacement until drawing a number $\leq k$. Denote the expected number of draws by $R(N,k)$. I want a good approximation for $\sum_{k=1}^N R(N,k)$.

I'm guessing this is a well known distribution, but I don't know how to search for it.

Update: The motivation is the following story. There are $N$ people, and $N$ items. Each person has a randomly uniformly drawn preference order over the $N$ items. The first person gets his favorite item, the second gets his favorite item out of what's left after the first person took his item, and so on, the $k$-th person gets his favorite item out of what's left after $1,..,k-1$ took theirs. So $R(N,N-k)-1$ is the expected number of items that person $k$ wanted but were already gone.

Thanks!

• This looks like homework (about the coupon collector problem). Care to explain the motivation? – Ori Gurel-Gurevich Nov 5 '12 at 3:16
• It is, except that you sample without replacement until getting a new coupon (when a new coupon arrives put all coupons back in). I updated to add motivation. Thanks! – user1707116 Nov 5 '12 at 18:48

The probability that it will take at least $m+1$ draws, i.e. that the first $m$ results are all numbers $> k$, is ${{N-k} \choose {m}}/{N \choose {m}}$ for $0 \le m \le N-k$. So $$R(N,k) = \sum_{m=0}^{N-k} \dfrac{{{N-k} \choose m}}{N \choose m} = \frac{N+1}{k+1}$$ So you want \eqalign{\sum_{k=1}^N \frac{N+1}{k+1} &= (N+1)(\Psi(N+2)-1+\gamma)\cr &= \left( \ln \left( N \right) -1+\gamma \right) N+\ln \left( N \right) +\frac12+\gamma+{\frac {5}{12N}}-\frac{1}{12 N^2}+{\frac {1}{ 120 N^3}}+{\frac {1}{120 N^4}}+O \left( \frac{1}{N^5} \right)\cr}
Here's a small alternative to Robert Israel's derivation of $R(N,k) = (N+1)/(k+1)$. On your first draw, you'll either be done, with probability $k/N$, or you'll continue with $N-1$ elements, with probability $(N-k)/N$. Hence
$$R(N,k) = {k\over N} 1 + {N-k\over N} (1+R(N-1,k)) = 1 + {N-k\over N}R(N-1,k)$$
(I suppose I could have skipped over the middle step: you definitely draw once, and you may have to keep drawing.) If, inductively, $R(N-1,k) = N/(k+1)$, then
$$R(N,k) = 1+{N-k\over N}{N\over k+1} = {N+1\over k+1}$$