Azuma's inequality

In probability theory, the Azuma–Hoeffding inequality (named after Kazuoki Azuma and Wassily Hoeffding) gives a concentration result for the values of martingales that have bounded differences. Suppose is a martingale (or super-martingale) and almost surely. Then for all positive integers N and all positive reals , And symmetrically (when Xk is a sub-martingale): If X is a martingale, using both inequalities above and applying the union bound allows one to obtain a two-sided bound: The proof shares similar idea of the proof for the general form of Azuma's inequality listed below. Actually, this can be viewed as a direct corollary of the general form of Azuma's inequality. Note that the vanilla Azuma's inequality requires symmetric bounds on martingale increments, i.e. . So, if known bound is asymmetric, e.g. , to use Azuma's inequality, one need to choose which might be a waste of information on the boundedness of . However, this issue can be resolved and one can obtain a tighter probability bound with the following general form of Azuma's inequality. Let be a martingale (or supermartingale) with respect to filtration . Assume there are predictable processes and with respect to , i.e. for all , are -measurable, and constants such that almost surely. Then for all , Since a submartingale is a supermartingale with signs reversed, we have if instead is a martingale (or submartingale), If is a martingale, since it is both a supermartingale and submartingale, by applying union bound to the two inequalities above, we could obtain the two-sided bound: We will prove the supermartingale case only as the rest are self-evident. By Doob decomposition, we could decompose supermartingale as where is a martingale and is a nonincreasing predictable sequence (Note that if itself is a martingale, then ). From , we have Applying Chernoff bound to , we have for , For the inner expectation term, since (i) as is a martingale; (ii) ; (iii) and are both -measurable as is a predictable process; (iv) ; By applying Hoeffding's lemma, we have Repeating this step, one could get Note that the minimum is achieved at , so we have Finally, since and as is nonincreasing, so event implies , and therefore Note that by setting , we could obtain the vanilla Azuma's inequality.