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.

See also matrix martingale inequalities.

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.

Bentkus-style inequality

Let $(X_i$) be a supermartingale adapted to $({\mathcal{F}}_i)$. If $a_i\le X_i\le b_i$, then

$$\mathbb{P}(S_n\ge u)\le \underset{\alpha \ge 1}{\inf }\underset{t}{\inf }\frac{\mathbb{E}(S_n-t{)}_{+}^{\alpha }}{(u-t{)}_{+}^{\alpha }}.$$

Similarly to Bentkus’ inequality for scalar random variables, this improves over the Chernoff method. We can further bound this as

$$\begin{array}{r}\underset{\alpha \ge 1}{\inf }\underset{t}{\inf }\frac{\mathbb{E}(S_n-t{)}_{+}^{\alpha }}{(u-t{)}_{+}^{\alpha }}\le \underset{\alpha \ge 1}{\inf }\underset{t}{\inf }\frac{\mathbb{E}({\sum }_i{G}_i-t{)}_{+}^{\alpha }}{(u-t{)}_{+}^{\alpha }}\le \underset{t}{\inf }\frac{\mathbb{E}({\sum }_i{G}_i-t{)}_{+}}{(u-t{)}_{+}}.\end{array}$$

where $G_i\in \{a_i,b_i\}$ and $\mathbb{E}{G}_i=0$. The right hand side can be computed explicitly, or approximated, in some circumstances. See here.

Bentkus-style inequality for variance

In addition to the boundedness condition above, suppose we also have $\mathbb{V}(X_i)\le {\sigma }_i^2$. Then we can write

$$\mathbb{P}(S_n\ge u)\le \underset{\alpha \ge 2}{\inf }\underset{t}{\inf }\frac{\mathbb{E}(S_n-t{)}_{+}^{\alpha }}{(u-t{)}_{+}^{\alpha }}.$$

As above, we can bound the right hand side with a worst case distribution. In particular, this time we have $G_i\in \{-{\sigma }_i^2/b_i,b_i\}$ and $\mathbb{E}{G}_i=0$.

References

• Concentration of Measure for the Analysis of Randomized Algorithms by Dubhashi and Panconesi.