4
$\begingroup$

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

Thanks for your help.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Morehand Dec 6 '19 at 6:59
  • $\begingroup$ @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$. $\endgroup$ – RRL Dec 6 '19 at 7:19
  • $\begingroup$ 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? $\endgroup$ – RRL Dec 6 '19 at 7:30
  • $\begingroup$ 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/… $\endgroup$ – Morehand Dec 6 '19 at 8:12
  • $\begingroup$ 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}$. $\endgroup$ – RRL Dec 6 '19 at 8:33
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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