Recurrence relations whose base case is 'at infinity' - MathOverflow

Recurrence relations whose base case is 'at infinity'

2010-10-09T13:42:35Z

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!

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.

Answer by Johan Wästlund for Recurrence relations whose base case is 'at infinity'

2012-01-04T13:36:13Z

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.