Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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! –  Hobbes Nov 5 '12 at 18:48
add comment

2 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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