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:
“A man willing to work, and unable to find work, is perhaps the saddest sight that fortune’s inequality exhibits under this sun.”
—Thomas Carlyle (1795–1881)