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:
“Ideas are refined and multiplied in the commerce of minds. In their splendor, images effect a very simple communion of souls.”
—Gaston Bachelard (1884–1962)
“The doctrine of equality!... But there exists no more poisonous poison: for it seems to be preached by justice itself, while it is the end of justice.... “Equality for equals, inequality for unequals”Mthat would be the true voice of justice: and, what follows from it, “Never make equal what is unequal.””
—Friedrich Nietzsche (1844–1900)
“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)