# 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.

-

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

1. $F_{n,n}$ and $G_{n,n}$ are very close to each other,
2. $G_{n,n} - F_{n,n}$ is decreasing,
3. $n - G_{n,n}$ is increasing,
4. $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.

-
@Shai Covo: Does my claim that $a_n < n$ for $n \geq 15$ agree with your numerical work? –  Mike Spivey Dec 16 '10 at 0:46
According to my results, $a_n < n$ for all $n \geq 10$. Thank you for this answer. I'll probably have a look at it tomorrow. –  Shai Covo Dec 16 '10 at 1:14
Very nice answer! (I went over it briefly.) Note that your sequence $a_m$ plays a central role in Ross Millikan's second answer, where it is denoted $E(n)$. –  Shai Covo Dec 17 '10 at 2:49

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.

-
Thanks for this answer. I'll go over it later on. –  Shai Covo Dec 15 '10 at 1:46
Can you elaborate on your conclusion "the number of steps to get the cut off up to n is about $\sum\nolimits_{d = 1}^n {\frac{{2n}}{{(d + 1)^2 }}}$"? Also, consider this sum for values of $n >> 100$. –  Shai Covo Dec 15 '10 at 8:01
If we are increasing E by $(d+1)/2n$ per step, to increase E by 1 when d is constant takes $2n/(d+1)^2$ steps. So my sum is the number of steps to increase E by 1 when d=1, plus the number of steps to increase E by 1 when d=2, and so on. For n->infinity, the sum is 2(pi^2/6-1)n=1.2898n –  Ross Millikan Dec 15 '10 at 13:56
Whereas, as you noted, for $n=100$ the sum agrees very well with the number of steps to get the cut off up to $n$, this is not so for values of $n >> 100$ (but that disagreement is in the right direction for our purpose). For example, for $n=10000$ the sum is $\approx 12897 \approx 2(\pi^2/6-1)n$, compared to a cutoff of $n$ at about $13520$. –  Shai Covo Dec 15 '10 at 15:06
I think the fault lies in the approximation that e is about 1/2. This is more important for large n/d. When e is small you get smaller steps, so it takes longer to get from e =1/2 to e=0 than from e=1- to e=1/2 and I think we are seeing that. Not sure, though. –  Ross Millikan Dec 15 '10 at 15:42

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

-
You mentioned math.stackexchange.com/questions/12485/…. Well, my answer there corresponds exactly to your answer. That sequence is indeed complicated, but note the end of that answer for a possible asymptotic result. –  Shai Covo Dec 15 '10 at 15:35
+1: Your answer, combined with mine at math.stackexchange.com/questions/12485/… , may lead to a solution. I'll check this out. –  Shai Covo Dec 15 '10 at 22:37