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 { 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 the method of bounded differences (MOBD) which is common in the analysis of randomized algorithms.
Read more about Azuma's Inequality: Simple Example of Azuma's Inequality For Coin Flips, Remark
Famous quotes containing the word inequality:
“Nature is unfair? So much the better, inequality is the only bearable thing, the monotony of equality can only lead us to boredom.”
—Francis Picabia (1878–1953)