Recurrence relations whose base case is 'at infinity' - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T14:25:58Z http://mathoverflow.net/feeds/question/41591 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41591/recurrence-relations-whose-base-case-is-at-infinity Recurrence relations whose base case is 'at infinity' Joseph O'Rourke 2010-10-09T13:42:35Z 2012-01-04T13:36:13Z <p>I ran across this recurrence relation in a paper by Medina and Zeilberger [MZ] (who got it from [CR]):</p> <p>$$f(h,t) = \max \left( \frac{1}{2} f(h+1,t) + \frac{1}{2} f(h,t+1) ,\frac{h}{h+t} \right) \;.$$</p> <p>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 <a href="http://math.stackexchange.com/questions/6195/why-is-this-coin-flipping-probability-problem-unsolved" rel="nofollow">this MSE posting</a>. 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].)</p> <p>My question is:</p> <blockquote> <p>Is there a class of recurrence relations that includes the above example, and for which some theory has been developed for solving such equations?</p> </blockquote> <p>Thanks for pointers and references!</p> <p><b>References</b></p> <p>[MZ] Luis A. Medina, Doron Zeilberger, "An Experimental Mathematics Perspective on the Old, and still Open, Question of When To Stop?" <a href="http://arxiv.org/abs/0907.0032" rel="nofollow">arXiv:0907.0032v2 [math.PR]</a></p> <p>[CR] Y.S. Chow and Herbert Robbins. On optimal stopping rule for $S_n/n$. <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.ijm/1256068146" rel="nofollow"><em>Ill. J. Math.</em>, 9:444–454, 1965</a>.</p> <p>[W] Julian D.A. Wiseman <a href="http://www.jdawiseman.com/papers/easymath/chow_robbins.html" rel="nofollow">web page</a>.</p> http://mathoverflow.net/questions/41591/recurrence-relations-whose-base-case-is-at-infinity/84883#84883 Answer by Johan Wästlund for Recurrence relations whose base case is 'at infinity' Johan Wästlund 2012-01-04T13:36:13Z 2012-01-04T13:36:13Z <p>For this specific recurrence, Olle Häggström and I have some results in the paper <a href="http://arxiv.org/pdf/1201.0626" rel="nofollow">arXiv:1201.0626 [math.PR]</a> that we just posted.</p> <p>The key lemma is based on Olle's trick that I also mentioned in an answer to <a href="http://mathoverflow.net/questions/63789/probability-of-a-random-walk-crossing-a-straight-line/64472#64472" rel="nofollow">this question</a>. </p> <p>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. </p> <p>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).$$</p> <p>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.</p>