10
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks a million for the reference! Since you are also the author, could you also tell me does the result generalise in a straightforward manner to super- and sub-martingales? I see they're mentioned at the start of section 8 using the notation $\frak M_-$ but they are not mentioned in Theorem 8.7. $\endgroup$ – Daron Feb 27 '19 at 11:58
  • $\begingroup$ @Daron : The answer is yes for supermartingales (see Theorem 8.2 in that paper), but likely no for submartingales (I don't have a counterexample for submartingales right away, but I guess it is not too hard to construct one). $\endgroup$ – Iosif Pinelis Feb 27 '19 at 13:18
  • $\begingroup$ Thanks. What I means was for submartingales does the Theorem still hold if we replace $X_j - X_0 \ge r$ with $X_j - X_0 \le r$? Since you say the original theorem holds for supermartingales that answers my question. $\endgroup$ – Daron Feb 27 '19 at 14:50
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.