# Secretary problem - Riemann integral

I was following the derivation for the famous secretary problem on Wikipedia and I was unsure about the step from the discrete summation to the Riemann integral. Namely, why does $$\frac1n\to dt$$ as $$n\to\infty$$? I thought $$\Delta t$$ was the width of the interval divided by $$n$$, but the width of this interval is $$1-x$$? Is it that the limits of $$\frac{1-x}n$$ and $$\frac1n$$ would be the same as $$n\to\infty$$?

The part of the derivation in the article alluding to a Riemann sum is hand-waving.

For a rigorous approach, write the discrete sum as

$$\tag{1}\frac{r-1}{n}\sum_{i=r}^n \frac{1}{i-1} = \frac{r-1}{n}\sum_{i=r-1}^{n-1} \frac{1}{i} = \frac{r-1}{n}\left(\frac{1}{r-1}+\sum_{i=r}^{n-1} \frac{1}{i}\right)\\ = \frac{1}{n} + \frac{r-1}{n}\left(\sum_{i=1}^{n-1} \frac{1}{i} - \sum_{i=1}^{r-1} \frac{1}{i}\right) \\ = \frac{1}{n} + \frac{r-1}{n}\left(\sum_{i=1}^{n-1} \frac{1}{i} - \log(n-1)- \left(\sum_{i=1}^{r-1} \frac{1}{i}- \log(r-1)\right)\right) + \frac{r-1}{n}\log \frac{n-1}{r-1}$$

We will let both $$r \to \infty$$ and $$n \to \infty$$, with $$\frac{r-1}{n}= x + \phi(n)$$ where $$x$$ is fixed and $$\phi(n) \to 0$$. For example, taking $$r = \lfloor 1+nx\rfloor$$ we have $$x - \frac{1}{n} < \frac{r-1}{n} \leqslant x$$ and $$\frac{r-1}{n} \to x$$ as $$n \to \infty$$.

Substituting $$x+ \phi(n)$$ for $$\frac{r-1}{n}$$ on the RHS of (1), we get

$$\tag{2}\frac{r-1}{n}\sum_{i=r}^n \frac{1}{i-1} = \frac{1}{n} + (x+\phi(n))\left(\sum_{i=1}^{n-1} \frac{1}{i} - \log(n-1)- \left(\sum_{i=1}^{r-1} \frac{1}{i}- \log(r-1)\right)\right) + (x + \phi(n))\log \frac{1-1/n}{x+\phi(n)}$$

Using $$\lim_{m \to \infty} \sum_{i=1}^m \frac{1}{i} - \log(m) = \gamma$$, where $$\gamma$$ is the Euler-Mascheroni constant, and taking the limit of both sides of (2) as $$n \to \infty$$, it follows that

$$\lim_{n \to \infty}\frac{r-1}{n}\sum_{i=r}^n \frac{1}{i-1}= 0 + x(\gamma - \gamma) + x \log \frac{1}{x} = -x\log(x) = x \int_x^1 \frac{dt}{t}$$

Note that the integral is a large-$$n$$ approximation for the probability that the best applicant is selected from a pool of $$n$$ applicants when the first $$x \cdot n$$ applicants are rejected.

• Thank you very much for your thorough answer. It is definitely more rigorous. That said, when you say x is fixed, do you mean x is the limit of (r-1)/n as both r and n tend to infinity? Also terms of intuition, how can I understand why the author was able to say limit 1/n = dt? – Morehand Dec 6 '19 at 6:59
• @Morehand: In the discrete setting $r$ and $n$ are integers. I am assuming that we specify a fixed value $x$ and for any $n$ we choose the $r$ such that$(r-1)/n$ is as close to $x$ as possible -- and $(r-1)/n \to x$ as $n \to \infty$. That is $r$ is the closest integer to $1+nx$. – RRL Dec 6 '19 at 7:19
• To make $\int_x^1 \frac{dt}{t}$ appear in $P(x)$ as $n \to \infty$ you need to arrive at a Riemann sum like $\frac{1-x}{n} \sum_{j=1}^n \frac{1}{x + (1-x)j/n}$ somewhere in the manipulation of the original discrete sum. I don't think it is possible to do this precisely for arbitrary $x$ when you start with $\sum_{i= r}^n \frac{1}{i-1}$. Nevertheless the Riemann sum associates $\frac{1-x}{n}$ with $dt$. Why do you think the author has anything rigorous in mind here? – RRL Dec 6 '19 at 7:30
• Rigour aside, how would the author even know its highly plausible? I saw similar derivations when searching online and each of them equated the limit of 1/n as n tends to infinity with dt, eg thebryanhernandezgame.files.wordpress.com/2010/05/… – Morehand Dec 6 '19 at 8:12
• It is plausible because if $r-1 \approx nx$, the sum is approximately $$x \left(\frac{1}{nx} + \frac{1}{nx+1} + \ldots +\frac{1}{nx + (n-1 - nx)}\right) = x \left(\frac{1}{x} + \frac{1}{x+1/n} + \ldots +\frac{1}{x + (n-1)/n - x)}\right)\frac{1}{n}$$ which looks a bit like a Riemann sum for $\int_x^1 \frac{dt}{t}$. – RRL Dec 6 '19 at 8:33

RRL very kindly provided a rigorous derivation and answered some of my follow up questions. Thank you.

I’ve also realised what I was missing re: the Riemann sum - when introducing 1/t = N/i, the summation increments are no longer 1 but 1/N. This is consistent with delta t in a Riemann sum, hence 1/N outside the brackets becomes dt as n tends to infinity.