Simple Example of Azuma's Inequality For Coin Flips
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 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.
Read more about this topic: Azuma's Inequality
Famous quotes containing the words simple, inequality and/or coin:
“a mind
That nobleness made simple as a fire,
With beauty like a tightened bow,”
—William Butler Yeats (1865–1939)
“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)
“Any language is necessarily a finite system applied with different degrees of creativity to an infinite variety of situations, and most of the words and phrases we use are “prefabricated” in the sense that we don’t coin new ones every time we speak.”
—David Lodge (b. 1935)