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:
“However energetically society in general may strive to make all the citizens equal and alike, the personal pride of each individual will always make him try to escape from the common level, and he will form some inequality somewhere to his own profit.”
—Alexis de Tocqueville (1805–1859)