An Experimental Mathematics Perspective on the Old, and still Open, Question of When To Stop?

By Luis A. Medina and Doron Zeilberger

[Appeared in "Gems in Experimental Mathematics", Contemporary Mathematics series (AMS) v. 517 (T. Amdeberhan, L. Medina, and V. Moll, eds.), 265-274.]
.pdf   .ps   LaTeX souce  
Written: June 23, 2009.
Ted Hill is not only a great probability theorist, but also an amazing writer. We were really fascinated by his recent American Scientist article, where he talked about the important problem, both in mathematics and in real life, of when to stop? The present article can be viewed as a footnote to one of the problems discussed by Hill.
Added Sept. 9, 2010: Read Julian Wiseman's amazingly precise estimate that explains why it is good to stop when you have 5 heads and 3 tails.
Added Jan. 23, 2012: If you are a skeptical mathematician, who only believes in rigorous proof, you should read Olle Haggstrom and Johan Wastlund's beautiful article that proves that if you have five heads and three tails, it is good to stop, and more importantly, a completely new approach for proving rigorously, using a computer (of course!), that it is good to stop when it is indeed the case.
Added Aug. 2, 2012: the present article is mentioned in Henk Tijms's delightful and insightful "semi-popular" article
Added Aug. 9, 2022: Read John Elton's beautiful article with precise asymptotics, using a "Catalan tree". It is a true masterpiece.

Maple and Mathematica Packages

Important: This article is accompanied by

Sample Input and Output

Sample Input and Output for the Maple package ChowRobbins

  • For the story of rewards and when to stop for all positions up to 10 coin-tosses
    the input gives the output.
  • For the (probably) sequence of stopping-times, βn for n between 1 and 100
    the input gives the output.
  • For the story of comparative gambling up to 6 coin-tosses, with different ambitions
    the input gives the output.

Sample Input and Output for the Maple package STADJE

  • For the story of the probabilities of escaping the region y ≥ ax/b for a walker in the square lattice with positive unit steps, starting at the origin, and equally likely to go up or right, for 2 ≤ b ≤ a ≤ 5 and also the larger probabibility of escaping y > ax/b (not counting the origin)
    the input gives the output.
  • For the first 20 terms of the sequences enumerating the number of walks, from the origin to (n,n), staying in the region y ≥ ax/b , and their leading asymptotics, for all 2 ≤ b ≤ a ≤ 6
    the input gives the output.
  • For the first 20 terms of the sequences enumerating the number of walks from the origin to (an,bn), staying in the region y ≥ ax/b , and their leading asymptotics, for all 2 ≤ b ≤ a ≤ 6
    the input gives the output.
Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page