Asymptotic behavior of the first step in a best strategy Consider the game described here, but for a sequence $X_1,\ldots,X_n$ of i.i.d. uniform rv's on $\lbrace 1,\ldots,n \rbrace$ (in the original game $n=6$). Using the original notation, let $a_n$ denote the first element in the best strategy $a_n,\ldots,a_2$. We saw that for $n=6$, $a_n = n$. Can you provide a heuristic explanation as to why $a_n < n$ for all sufficiently large $n$ (this is indicated by numerical results), or even much better, can you determine the behavior of $n - a_n$ as $n \to \infty$? No rigorous proof is required, only heuristic ideas.
 A: Update: See the last section for a possible proof (**) that $a_n < n$ for all $n \geq 18$.

Here are some bounds on $E(n,m)$ that turn out to be useful.
Using $E_{n,m}$ for $E(n,m)$ in Ross Millikan's notation, let $R_{n,m} = \lceil E_{n,m} \rceil - E_{n,m}$.
Simplifying the expression for $E_{n,m}$ in Ross's first answer yields (thanks to some nice cancellation)
$$E_{n,m} = \frac{n+1}{2} + \frac{E_{n,m-1}(E_{n,m-1}-1)}{2n} - \frac{R_{n,m-1}(R_{n,m-1}-1)}{2n}.$$
Since $0 \leq R_{n,m-1} < 1$, we have $$0 \leq - \frac{R_{n,m-1}(R_{n,m-1}-1)}{2n} \leq \frac{1}{8n}.$$  This can be seen easily by the fact that the expression being bounded is quadratic in $R_{n,m-1}$ with vertex at $R_{n,m-1} = \frac{1}{2}$.
Therefore, $F_{n,m} \leq E_{n,m} \leq G_{n,m}$, where $F_{n,1} = G_{n,1} = \frac{n+1}{2}$, and
$$F_{n,m} =  \frac{n+1}{2} + \frac{F_{n,m-1}(F_{n,m-1}-1)}{2n},$$
$$G_{n,m} =  \frac{n+1}{2} + \frac{G_{n,m-1}(G_{n,m-1}-1)}{2n} + \frac{1}{8n}.$$
Thus we have recurrences that give upper and lower bounds on $E_{n,m}$ without having to deal with the problem of taking ceilings.
Numerical experiments indicate that 


*

*$F_{n,n}$ and $G_{n,n}$ are very close to each other,

*$G_{n,n} - F_{n,n}$ is decreasing,

*$n - G_{n,n}$ is increasing, 

*$n - G_{n,n} > 1$ for $n \geq 15$.


A proof of 3 or 4 would imply $a_n < n$ for $n \geq 15$.  A close analysis of $G_{n,n} - F_{n,n}$, together with an asymptotic estimate of $F_{n,n}$ or $G_{n,n}$, would help with the requested behavior of $n - a_n$.  
Also, it is easy to see that $F_{n,m} = n$ is an equilibrium solution for the $F_{n,m}$ recurrence.  That should be helpful as well.

It turns out that $G_{n,m} = \frac{1}{2} + n a_m$, where $a_1 = \frac{1}{2}$ and $a_m$ satisfies the recurrence $$a_m = \frac{a^2_{m-1}+1}{2}.$$  This is easy to verify once one has the conjectured expression.
It also turns out that the $a_m$ recurrence has been studied (**), with the following bounds:
$$ 1 - \frac{2}{m} + \frac{2}{m^2} \ln \frac{m}{3} + \frac{417}{128m^2} \leq a_m \leq 1 - \frac{2}{m} + \frac{5 \ln m + 3}{2m^2}$$
The upper bound implies 
$$G_{n,n} \leq \frac{1}{2} + n \left(1 - \frac{2}{n} + \frac{5 \ln n + 3}{2n^2}\right) = n - \frac{3}{2} + \frac{5 \ln n + 3}{2n} (*) $$
Now, since $E_{n,n} \leq G_{n,n}$, $G_{n,n} < n-1$ implies $a_n < n$.  The expression on the right in $(*)$ is less than $n-1$ when $$\frac{5 \ln n + 3}{2n} < \frac{1}{2},$$
which is true for all $n \geq 18$.
(**) The bounds required for my argument are given in a post in the "Real Analysis Unsolved and Proposed Problems" forum at the Art of Problem Solving.  I cannot tell whether the bounds are conjectured and the poster is asking for a proof, or whether the poster has a proof and is merely posing the problem for others to solve.  So I cannot claim that this is a complete proof.
A: If we let $E(n,m)$ be the expectation with m throws of an n sided die, we will accept the $m^{th}$ to last throw if it is $\geq E(n,m-1)$, so $E(n,1)=\frac{n+1}{2}$ and $$E(n,m)=\frac{(n-\lceil E(n,m-1)\rceil +1)}{n}\frac{(n+\lceil E(n,m-1)\rceil )}{2}+\frac{\lceil E(n,m-1)\rceil -1}{n}E(n,m-1)$$  where the first term comes from accepting the throw and the second is from rejecting it.  Letting $n-\lceil E(n,m-1)\rceil=d$ (the whole part of the difference) and $\lceil E(n,m-1)\rceil-E(n,m-1)=e$ (the fractional part) we find $$E(n,m)-E(n,m-1)=\frac{d^2+(1+2e)d+2e}{2n}$$  If we figure that e averages about 1/2, this means we increase E by $\frac{(d+1)^2}{2n}$ per step.  The number of steps to get the cut off up to n is about $$\sum_{d=1}^{n}{\frac{2n}{(d+1)^2}}$$  For n=100, I find by explicit calculation we hit a cutoff of 99 (E>98) at m=75 and a cutoff of 100 (E>99) at m=129.  The sum comes out just about 128.  We can find lower cutoffs by raising the lower limit of the sum.
A: Thinking more, as n gets large we can pass to the continuous case and get rid of the ceilings and e.  So imagine we are pulling numbers from [0,1] n times and each time you can accept it and take the value or decline it and take your future chances.  Let E(n) be the expectation value of n pulls.  Again, when you have n pulls left you should accept anything greater than E(n-1).  So the recurrence is $E(n)=(1-E(n-1))\frac{1+E(n-1)}{2}+E(n-1)^2$ or $E(n)=\frac{1+E(n-1)^2}{2}$  I think we were told here  that sequences involving E(n-1)^2 are very hard.  In the current case the E(n-1)^2 is divided by 2 but we can take that out by rescaling to D=2E and we have $D(n)=D(n-1)^2+\frac{1}{2}$ with D(1)=1
