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!



Sampling without replacement until hitting a subset
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}$$


