• Abstract:   Let H  be the class of discrete real-valued martingales X₀ = 0, X₁, ..., X_n such that for each i, |X_i - X_i-1| < 1. Define, for all non-negative integers n, and a>0, the ``truncated coin flips'' martingale, which, conditioned on any value X<sub>i-1</sub> = x < a, maximizes the probability that a - X<sub>i</sub> is either zero or a positive integer with the same parity as the number of steps remaining, n-i. We prove that this maximizes Pr ( X<sub>n</sub> > a ) over all martingales (X<sub>i</sub>) in H. We also show that this is essentially the unique martingale with this extremal property. The proof uses ``retrograde analysis,'' to prove that, under certain circumstances, a gambler's best strategy is the truncated coin flips martingale.

  Our work gives a simple alternative proof of the well-known Hoeffding-Azuma inequality.

Versions available:

Last modified, February 2003.

PDF

Postscript

DVI