Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
@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
add comment

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.

share|improve this answer
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
show 1 more comment

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

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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