A large deviation inequality for vector valued martingales

Thomas P. Hayes. 15 May, 2001.
Communicated by Laszlo Babai.


We prove a generalization of Azuma's Inequality which holds for vector-valued martingales in Euclidean space of any dimension.

Our result also holds for Euclidean-valued weak martingales, and random processes with even weaker conditioning. We show moreover that a large class of large-deviation inequalities must hold in this more general context whenever they hold for the class of martingales.

As an application, we answer two questions posed by L. Babai about the Fourier coefficients of random subsets of a finite abelian group.

Original Document

The original document is available in Postscript (uploaded 8 June, 2001 by Dustin Mitchell).

Additional Document Formats

The document is also available in DVI (uploaded 8 June, 2001 by Dustin Mitchell) and PDF (uploaded 8 June, 2001 by Dustin Mitchell).

NOTE: The author warrants that these additional documents are identical with the originial to the extent permitted by the translation between the various formats. However, the webmaster has made no effort to verify this claim. If the authenticity of the document is an issue, please always refer to the "Original document." If you find significant alterations, please report to