Geometric convergence of algorithms in gambling theory (Q2757550)

When a gambling problem in the sense of \textit{L. E. Dubins} and \textit{L. J. Savage} [``How to gamble if you must. Inequalities for stochastic processes'' (1965; Zbl 0133.41402)] is leavable (i.e. a stop rule is selected in addition to a strategy \(\sigma\) available at \(x\)), a backward induction provides an algorithm for calculating the optimal return [see \textit{A. P. Maitra} and \textit{W. D. Sudderth}, ``Discrete gambling and stochastic games'' (1996; Zbl 0864.90148)]. For nonleavable problems there exists a relatively new algorithm [see \textit{L. Dubins}, \textit{A. Maitra}, \textit{R. Purves} and \textit{W. Sudderth}, Isr. J. Math. 67, No. 3, 257-271 (1989; Zbl 0694.60038)].NEWLINENEWLINENEWLINEIn the paper it is proved for the leavable problem that if the state space \(S\) is finite and if for every \(x\in S\), \(\Gamma(x)\) is finite (\(\Gamma\) is the gambling house), then the algorithm converges geometrically fast. For the nonleavable problem the same result which does not require the hypothesis that the \(\Gamma(x)\) are finite is obtained.