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.


  • 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
up vote 1 down vote accepted

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}$$

follows. (I'm omitting some of the niceties of a proper proof by induction, but I don't think I'm skipping anything essential or skating on any thin ice.)

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.