MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I ran across this recurrence relation in a paper by Medina and Zeilberger [MZ] (who got it from [CR]):

$$f(h,t) = \max \left( \frac{1}{2} f(h+1,t) + \frac{1}{2} f(h,t+1) ,\frac{h}{h+t} \right) \;.$$

The "base" condition of the recurrence is that, for $h+t = \infty$, $f(h,t)=\frac{1}{2}$. This function $f$ represents the expected gain in a paricular coin game ($h$ and $t$ are heads and tails), explained in this MSE posting. I had not before encountered recurrence relations whose "initial conditions" are "at infinity," and was surprised to learn that there is no known explicit solution for $f$. (However, one can compute particular values numerically by limiting to $n$ trials and letting $n \rightarrow \infty$. For example, $f(5,3) =\max ( 0.62361957757, 5/8 )$. See [W].)

My question is:

Is there a class of recurrence relations that includes the above example, and for which some theory has been developed for solving such equations?

Thanks for pointers and references!


[MZ] Luis A. Medina, Doron Zeilberger, "An Experimental Mathematics Perspective on the Old, and still Open, Question of When To Stop?" arXiv:0907.0032v2 [math.PR]

[CR] Y.S. Chow and Herbert Robbins. On optimal stopping rule for $S_n/n$. Ill. J. Math., 9:444–454, 1965.

[W] Julian D.A. Wiseman web page.

share|cite|improve this question
This problem is a lot like pricing a perpetual american option (google should give plenty of hits). The main difference that I see here is that the payoff depends on the proportion of heads, so that you are dividing by the number of trials (which translates to the time at which the option is exercised). In option pricing you would discount at some interest rate, which is a factor exponentially decaying in the exercise time. – George Lowther Oct 9 '10 at 15:18

For this specific recurrence, Olle Häggström and I have some results in the paper arXiv:1201.0626 [math.PR] that we just posted.

The key lemma is based on Olle's trick that I also mentioned in an answer to this question.

Briefly, the argument is this (see our abstract or the link in the OP for a description of the game): If at some point in the game we condition on the event of ever reaching a proportion of (at least) $p$ of heads, then as long as we haven't, the conditional probability of heads in the next toss is at least $p$. Now, one way of showing that an event is unlikely is to show that strange things happen if we condition on it. If the conditional probability of a long run of heads is very different from the unconditional one, then the probability of ever reaching proportion $p$ of heads must be small.

After pursuing the calculations, our main result (in the notation of the OP) is $$f(h,t) \leq \max\left(\frac{h}{h+t}, \frac12\right) + \min\left(\frac14\sqrt{\frac{\pi}{h+t}}, \frac1{2\cdot\left|h-t\right|}\right).$$

This allows us to compute $f(h,t)$ to any desired precision, and to verify rigorously that $f(h,t) = h/(h+t)$ in a number of cases. For instance, $f(5,3) = 5/8$, which means that in the Chow-Robbins coin flipping game, stopping is optimal with 5 heads and 3 tails.

share|cite|improve this answer

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.