Azuma’s Inequality
The Chernoff bound gives the concentration of sums of independent random variables. The concentration result can be generalized to martingales. Martingales and Azuma’s Inequality A sequence of random variables \(X_0, X_1, \ldots, X_n\) is called a martingale if \[ {\bf …