Geometric Convergence of Algorithms in Gambling Theory
S. Ramakrishnan, William D. Sudderth · Mathematics of Operations Research · 1998
In the Dubins and Savage theory of gambling, backward induction provides an algorithm for calculating the optimal return when the gambling problem is leavable. A relatively new algorithm works for nonleavable problems. We show that these algorithms converge geometrically fast for finite gambling problems. Our argument also provides a much simpler proof of convergence for the nonleavable case.