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:
“It is a curious emotion, this certain homesickness I have in mind. With Americans, it is a national trait, as native to us as the rollercoaster or the jukebox. It is no simple longing for the home town or country of our birth. The emotion is Janus-faced: we are torn between a nostalgia for the familiar and an urge for the foreign and strange. As often as not, we are homesick most for the places we have never known.”
—Carson McCullers (1917–1967)
“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)
“It is not funny that a man should be killed, but it is sometimes funny that he should be killed for so little, and that his death should be the coin of what we call civilization.”
—Raymond Chandler (1888–1959)