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:
“All the aspects of this desert are beautiful, whether you behold it in fair weather or foul, or when the sun is just breaking out after a storm, and shining on its moist surface in the distance, it is so white, and pure, and level, and each slight inequality and track is so distinctly revealed; and when your eyes slide off this, they fall on the ocean.”
—Henry David Thoreau (1817–1862)