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. 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 { Xk : k = 0, 1, 2, 3, ... } is a martingale (or super-martingale) and almost surely. Then for all positive integers N and all positive reals t, 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: Azuma's inequality applied to the Doob martingale gives McDiarmid's inequality which is common in the analysis of randomized algorithms. Let Fi be a sequence of independent and identically distributed random coin flips (i.e., let Fi be equally likely to be −1 or 1 independent of the other values of Fi). Defining X i = ∑ j = 1 i F j {displaystyle X_{i}=sum _{j=1}^{i}F_{j}} yields a martingale with |Xk − Xk−1| ≤ 1, allowing us to apply Azuma's inequality. Specifically, we get For example, if we set t proportional to n, then this tells us that although the maximum possible value of Xn scales linearly with n, the probability that the sum scales linearly with n decreases exponentially fast with n. If we set t = 2 n ln ⁡ n {displaystyle t={sqrt {2nln n}}} we get: