• Abstract:   Let X = (X₀ , ..., X_n ) be a discrete-time martingale taking values in any real Euclidean space such that X₀ = 0 and for all n, ||X_n - X_n-1|| < 1. We prove the large deviation bound

  Pr ( ||X_n|| > a )   <   2 e^{1-(a-1)2 / 2n}   <   2 e² e^{-a2 / 2n} .

  This upper bound is within a constant factor, e², of the Azuma-Hoeffding Inequality for real-valued martingales. This improves an earlier result of O. Kallenberg and R. Sztencel (1992). Our inequality holds even for ``very-weak martingales,'' namely, discrete stochastic processes X  which satisfy

  for every n,     E ( X_n | X_n-1 ) = X_n-1.

  In particular, this includes the class of weak martingales. More generally, we prove that, for every very-weak martingale X  in R^d, there exists a martingale Y  in R^d  such that for all n, the distribution of (Y_n-1, Y_n) is the same as that of (X_n-1, X_n). As an application, we answer questions posed by L. Babai about Fourier coefficients of random subsets of a finite abelian group.

Versions available:

Micro-revision, July 2005, corrects a typo in the abstract. Also, now with hyperlinked references.	PDF	Postscript	DVI
Resubmitted version, last modified February 2003.	PDF	Postscript	DVI