Azuma's Inequality and Concentration

Azuma’s inequality is a useful result concerning martingales. A (discrete-time) martingale is a stochastic process \(X_0, X_1, \ldots \) which satisfies*

$$\mathbf{E}(|X_i|) < \infty$$

for all \(i\), and

$$\mathbf{E}(X_{n+1} | X_1, \ldots, X_n) = X_n.$$

Roughly speaking, martingales corresponding to fair betting games: if \(X_n\) is my fortune after \(n\) rounds of a game, my expected fortune after playing the \((n+1)\)-st round is equal to my fortune before playing that round.

Azuma’s inequality applies to martingales in which the differences \(|X_{n+1} – X_n|\) are bounded. Specifically, suppose

$$|X_{i+1} – X_i| \leq c_i$$

for some constants \(c_i\) for \(i = 1, 2, \ldots, m\). Define \(C = \sum_{i = 1}^m c_i\). Then Azuma’s inequality states that

$$\mathbf{P}(X_m – X_0 > \lambda) < e^{- \lambda^2 / C}.$$

That is, the martingale \(X_1, X_2, \ldots, X_m\) is tightly concentrated around its expectation.

I just posted an essay which gives some applications of Azuma’s inequality to combinatorics and theoretical computer science, which is available here. Azuma’s inequality is an example of the concentration of measure phenomenon, which has rich applications in combinatorics, probability theory and Banach space theory. This book gives a very thorough survey of the phenomenon, although it approaches the subject from a very geometric/measure theoretic standpoint. A more condensed (and perhaps user-friendly) overview is available on Terence Tao’s blog.

Will Rosenbaum

Saarbrücken, Germany

comments powered by Disqus