martingale concentration

Let $(S_t)$ be a martingale wrt to the filtration $({\mathcal{F}}_t)$. Assume $(S_t)$ is scalar-valued unless otherwise indicated. Here we investigate concentration inequalities for $(S_t)$.

Note that martingale concentration inequalities generalize concentration inequalities for independent random variables (eg bounded scalar concentration), since we may take $S_t={\sum }_{i\le t}(X_i-\mu )$, in which the following bounds translate into bounds on ${\sum }_{i\le t}{X}_i$.

While we state concrete, mostly fixed-time results here, we note that many of the following bounds were made time-uniform (and often tightened) using sub-psi processes.

Azuma-Hoeffding inequality

Assume that $|X_t-X_{t-1}|\le c_t$ for all $t$, i.e., the martingale has bounded increments. Then, for all $n$,

$$\mathbb{P}(|X_n-X_0|\ge ϵ)\le 2\exp \left(\frac{-{ϵ}^2}{2{\sum }_{t=1}^n{c}_t^2}\right).$$

The natural one-sided versions of this inequality also exist. Note that $n$ is fixed in advance here (i.e., it is fixed-time result).

Dubins-Savage inequality

This is often considered Chebyshev’s inequality for martingales. If $(X_t)$ has conditional means ${\mu }_t$, i.e., $\mathbb{E}[X_t|{\mathcal{F}}_{t-1}]={\mu }_t$ and conditional variances $V_t=\mathbb{V}(X_t|{\mathcal{F}}_{t-1})$ then for any $a,b>0$,

$$\mathbb{P}\left(\exists t\ge 1:\sum _{i\le t}(X_i-{\mu }_i)\ge a+b\sum _{i\le t}{V}_i\right)\le \frac{1}{ab+1}.$$

This is a time-uniform result. This result can also be generalized to infinite variance. If $v_t(p)=\mathbb{E}[|X_t-{\mu }_t{|}^p|{\mathcal{F}}_{t-1}]$ for $1<p\le 2$, then

$$\mathbb{P}\left(\exists t\ge 1:\sum _{i\le t}(X_i-{\mu }_i)\ge a+b\sum _{i\le t}{v}_i(p)\right)\le \frac{1}{(c_{p}a{b}^{\frac{1}{p-1}}+1{)}^{p-1}},$$

where $c_p$ is a constant dependent on $c$. This was proven by Kahn in 2009.

Variance bound

If the martingale has bounded increments and the variance of the increments are also bounded, i.e.,

$$\mathbb{E}[|X_t-X_{t-1}{|}^2|{\mathcal{F}}_{t-1}]\le v_t^2,$$

then we can modify Azuma’s bound to read

$$\mathbb{P}(|X_n-X_0|\ge ϵ)\le 2\exp \left(\frac{-{ϵ}^2}{4V}\right),$$

where $V={\sum }_i{v}_i^2$, as long as $ϵ\le 2V/{\max }_i{c}_i$. Why is this better than Azuma’s inequality? Since the increments are bounded by $c_t$, a trivial bound on $\mathbb{E}[|X_t-X_{t-1}{|}^2|{\mathcal{F}}_{t-1}]$ is $c_t^2$. Thus we may assume that $v_t^2\le c_t^2$, which means the right hand side of the bound is tighter.

This was first proved by DA Grable in A Large Deviation Inequality for Functions of Independent, Multi-way Choices. A modern proof is given by Dubhasi and Panconesi in their textbook, Concentration of Measure for the Analysis of Randomized Algorithms, Chapter 8.

Variance bound — matrix version.

Suppose $(Z_t)$ is a matrix-valued martingale (Hermitian Matrices). Let $D_i=Z_i-Z_{i-1}$ and suppose

$$\left|D_i\right|\le c_i,\left|\mathbb{E}[D_i^2|{\mathcal{F}}_{i-1}]\right|\le {\sigma }_i^2.$$

Then, for $V={\sum }_{i\le n}{\sigma }_i^2$,

$$\mathbb{P}(\left|Z_n\right|>ϵ)\le 2d\exp \left(\frac{-{ϵ}^2}{4V}\right),$$

where each $Z_t$ is a $(d\times d)$-matrix. This was first proved by David Gross: Recovering Low-Rank Matrices From Few Coefficients In Any Basis.

References

• Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi.
• Recovering Low-Rank Matrices From Few Coefficients In Any Basis, David Gross