Detailed analysis of the secretary problem

Solution 1:

Since the fractional part of $N/e$, calculated over the integers $N$, is uniformly distributed $\bmod 1$ (this can be checked by the Weyl's criterion), the result that $$\frac{N}{e}-1 <R<\frac{N}{e}+1$$ might suggest that $R=\lfloor N/e\rfloor$ and $R=\lceil N/e\rceil$ occur with equal probability.

However, as shown in the calculations of the OP, the correct result for the range of $R$ is

$$\frac{N}{e}-1 <R<\frac{N}{e}+1-\frac{1}{e}$$

The central value of this interval is $N/e-1/(2e)$, so the expected value of its fractional part is not $1/2$, but $1/2-1/(2e)$.

Assuming that the probabilities that $R=\lfloor N/e\rfloor$ and $R=\lceil N/e\rceil$ are linearly related to the closeness of this central value with $\lfloor N/e\rfloor$ and $\lceil N/e\rceil$, we get that the expected proportion of cases where $R=\lfloor N/e\rfloor$ is

$$1-\left(\frac{1}{2}-\frac{1}{2e}\right) \approx 0.6839$$

in accordance with the observed experimental value shown in the plot of the OP.

After some constructive comments on the possibility to improve the bounds for $R$, the idea to calculate the integral between $k-1/2$ and $k+1/2$ gives interesting results and confirms the value above.

Since we have $$1<\sum_{k=R}^{N-1}\frac1k<\sum_{k=R}^{N-1}\int_{k-1/2}^{k+1/2}\frac{\mathrm{d}x}{x}=\int_{R-1/2}^{N-1/2}\frac{\mathrm{d}x}{x}=\ln{\frac{N-1/2}{R-1/2}}$$ then $$R<\frac Ne +\frac 12-\frac 1{2e}$$

Also, since as $k\rightarrow \infty$ we have $$ 1>\sum_{k=R+1}^{N-1}\frac1k>\sum_{k=R+1}^{N-1}\int_{k-1/2+\epsilon}^{k+1/2+\epsilon}\frac{\mathrm{d}x}x=\int_{R+1/2+\epsilon}^{N-1/2+\epsilon}\frac{\mathrm{d}x}x= \ln{\frac {N-1/2+\epsilon}{R+1/2+\epsilon}}$$ we get the asymptotic lower bound $$R>\frac Ne -\frac 12-\frac 1{2e}$$

Collecting both results we finally have the optimized bounds

$$\frac Ne -\frac 12-\frac 1{2e}<R<\frac Ne +\frac 12-\frac 1{2e}$$

which numerically corresponds to the approximate interval

$$\frac Ne -0.6839<R<\frac Ne +0.3161 $$

Note that the interval identified by the bounds asymptotically converges to $1$. Therefore, for any value of $N/e$, only one among $\lfloor N/e \rfloor$ and $\lceil N/e \rceil$ is a possible value of $R$, being included in the range. Reminding the equidistribution $\bmod 1$ of $N/e$, we get that the probability that the floor function is selected is $$1/2+1/(2e)\approx 0.6839$$

Lastly, it should be noted that these bounds represent the best possible ones (otherwise there would be some $N$ for which no $R$ is allowed).