Detailed analysis of the secretary problem

The secretary problem is well-known. $N>2$ candidates present themselves for a job. You must either hire a candidate immediately after interviewing him, or let him go. The strategy you follow is to reject the first $R$ candidates, and then hire the first candidate who is better than all others you have interviewed so far. The problem is to find the value of $R$ that maximizes the probability of hiring the best candidate, and the usual answer given is to reject $frac Ne$ candidates.

In fact, one can show that the optimum number of candidates to reject is the greatest integer $R$ such that $$sum_{k=R}^{N-1}frac1k>1,$$ and that this number is always one of the two integers closest to $frac Ne$. I’ll defer the proofs of these assertions in order to get right to my question.

I guessed that the optimum value of $R$, which I’ll call $R_N$ would be equal to $leftlfloorfrac Nerightrfloor$ about half the time, but it seems that it’s actually best about two-thirds of the time. The graph below plots $$y_K=frac1{K-2}sum_{N=3}^Kleft[R_N=leftlfloorfrac Nerightrfloorright], 100leq Kleq1000$$ where $[cdot]$ is the Iverson bracket: $$[P]=cases{1,& if $P$ is true\0,& if $P$ is false}$$

While there’s a lot of oscillation, it does seem as though $lim_{Ktoinfty}y_K$ may well exist, and it certainly seems that $liminf_{Ktoinfty}y_K>frac12$.

I would like to investigate this, but I have no idea how to approach it. It seems like numerical analysis of the harmonic numbers must enter into it, but how to pick out the fraction of times that the floor is better than the ceiling?

Can you give me any suggestions of what kind of techniques might apply and where to learn about them? I put the analytic number theory tag on because I couldn’t think of anything better.

Here are the easy proof of the facts stated earlier.

Suppose the best candidate is the $k$th interviewed. Clearly, there is no chance of success unless $k>R$. Then we succeed if and only if the best candidate among the first $k-1$ interviewed was one of the first $R$. The probability of success is $$w_R := frac1Nsum_{k=R+1}^Nfrac R{k-1}=frac RNsum_{k=R}^{N-1}frac1{k}$$

Now $$begin{align}
w_{R+1}-w_R&=frac {R+1}Nsum_{k=R+1}^{N-1}frac1{k}-frac RNsum_{k=R}^{N-1}frac1{k}\
&=left(frac{R+1}N-frac RNright)sum_{k=R+1}^{N-1}frac1k-frac R{NR}\
&=frac1Nleft(sum_{R+1}^{N-1}frac1k-1right)
end{align}$$
so that $w_{R+1}>w_R$ if and only if $sum_{R+1}^{N-1}frac1k>1$. That is, the optimum number is of candidates to reject is the greatest integer $R$ such that $$sum_R^{N-1}frac1k>1.$$

(It is well-known that there are no positive integers $n>m$ such that $sum_{k=m}^nfrac1k=1,$ so there is no ambiguity.)

Given $N$, let $R$ be determined as above. I claim that $R$ is one of the two integers closest to $frac Ne$. We have $$1<sum_{k=R}^{N-1}frac1k<sum_{k=R}^{N-1}int_{k-1}^kfrac{mathrm{d}x}{x}=int_{R-1}^{N-1}frac{mathrm{d}x}{x}=ln{frac{N-1}{R-1}}$$ so that $$R<1+frac{N-1}{e}<1+frac Ne.$$

Also, we have $$
1>sum_{k=R+1}^{N-1}frac1k>sum_{k=R+1}^{N-1}int_k^{k+1}frac{mathrm{d}x}x=int_{R+1}^Nfrac{mathrm{d}x}x= ln{frac N{R+1}}$$ so that
$$R>frac Ne -1.$$