Can we do better than Azuma-Hoeffding when the variance is small?

Question

The Azuma-Hoeffding Inequality says that if $X_1,X_2, \ldots$ is a martingale and the differences are bounded by constants, $\|X_i - X_{i-1}\| \le 1$ say, then we should not expect the difference $\|X_N - X_0\|$ to grow too fast. Formally we have

$$P\left(|X_N -X_0| > \epsilon N\right) \le \exp\Big ( \frac{- \epsilon^2 N}{2 }\Big) \mbox{ for any }\epsilon > 0.$$

Note the inequality has nothing to do with how spread out the variables $X_i$ are. It only uses how the differences are bounded. In case all $X_i$ have small variance we'd expect stronger concentration results.

For example suppose the $A_1 , A_2, \ldots$ are drawn independently from $\mathcal N(0,\sigma^2)$ distributions cut off outside $[-1,1]$ and each $X_i = A_1 + \ldots + A_i$. The above inequality does not distinguish between the cases when $\sigma^2$ is large and small. When it is smaller we should expect a stronger concentration around the mean. In the degenerate case when $\sigma^2=0$ and all $A_i \equiv 0$ the left-hand-side will be exactly zero.

Are there any modifications of Azuma-Hoeffding that take into account the variances of the conditined variiables $ X_{i+1} | X_i, \ldots, X_1$ ? So far I have only found this paper in information theory. The theorem 2 is a version of AH that involves the variance. However that paper is quite recent, and it seems likely the problem has been considered by probabilists in the past.

Can anyone point me in the right direction?

Answer 1

Exponential inequalities for sums of independent random variables (r.v.'s) can be extended to martingales in a standard and completely general manner; see Theorem 8.5 or Theorem 8.1 for real-valued martingales, and Theorem 3.1 or Theorem 3.2 for martingales with values in 2-smooth Banach spaces in this paper.

In particular, Theorem 8.7 in the same paper implies the following martingale version of the Bennett (8b)--Hoeffding (2.9) inequality given for sums of independent r.v.'s:

If $(X_j)_{j=0}^n$ is a real-valued martingale with respect to a filter $(F_j)_{j=0}^n$ of $\sigma$-algebras such that for $d_j:=X_j-X_{j-1}$ we have $|d_j|\le a$ and $\sum_1^n E(d_j^2|F_{j-1})\le b^2$ for some real $a,b>0$ and all $j$, then \begin{equation} P(X_j-X_0\ge r)\le\exp\Big\{\frac{b^2}{a^2}\,\psi\Big(\frac{ra}{b^2}\Big)\Big\} \end{equation} for $r\ge0$, where $\psi(u):=u-(1+u)\ln(1+u)$.

According to Theorem 3, this bound is the best possible exponential bound on $P(X_j-X_0\ge r)$ in terms of $a,b^2,r$.

Answer 2

Adding to Iosif Pinelis' answer, there are two points here. First, as he says, the fact that we have a martingale rather than i.i.d. variables doesn't change much as proofs generally extend. So, second is what bounds are available for i.i.d. variables.

Others have mentioned keywords including Bennet's, Bernstein, Freedman inequalities. Another not yet mentioned is based on subgaussian variables. For example, Normal$(\mu,\sigma^2)$ variables are $\sigma^2$-subgaussian (even without restricting them to a bounded region!), and a sum of $N$ of them is $N\sigma^2$-subgaussian, so it satisfies

$$ \Pr\left[ |X_N - \mathbb{E} X| \geq \epsilon N \right] \leq 2 \exp\left(\frac{- N \epsilon^2}{2 \sigma^2} \right) $$

More details: A variable is $\sigma^2$-subgaussian if $\mathbb{E} e^{\lambda Y} \leq e^{\frac{\lambda^2 \sigma^2}{2}}$ for all $\lambda \in \mathbb{R}$. A sum of a $\sigma_1^2$ and a $\sigma_2^2$ subgaussian variable, independent, is $\sigma_1^2 + \sigma_2^2$ subgaussian (this extends immediately to martingales). A $\sigma^2$-s.g. variable satisfies the tail bound $\Pr[Y - \mathbb{E} Y \geq t] \leq e^{\frac{-t^2}{2\sigma^2}}$ on both sides. I wouldn't be surprised if something close to Iosif Pinelis' example result can be derived from a fact about subgaussian parameters of bounded variables, but I don't know that fact/proof myself offhand.

You can find more in the "Concentration Inequalities" book of Boucheron et al, for example.