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.

proportionof 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