Simple example of Azuma's inequality for coin flips

From Wikipedia, the free encyclopedia

You have new messages (last change).
It has been suggested that this article or section be merged into Azuma's inequality. (Discuss)

Let Fi be a sequence of independent and identically distributed random coin flips (i.e., let Fi be equally like to be +1 or −1 independent of the other values of Fi). Defining X_i = \sum_{j=1}^i F_j yields a martingale with |X_{k}-X_{k-1}|\leq 1, allowing us to apply Azuma's inequality. Specifically, we get

\Pr[X_N > X_0 + t] \leq \exp\left(\frac{-t^2}{2 N}\right).

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.

Retrieved from "http://en.wikipedia.org../../../s/i/m/Simple_example_of_Azuma%27s_inequality_for_coin_flips_11c3.html"