# Adaptive version of the Azuma–Hoeffding inequality

The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition: $$|X_k - X_{k-1}| \leq c_k$$ Then: $$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 \ln(1/\delta)}\right] \leq \delta$$

My question is:

Does the same inequality hold if the constants $c_k$ are not fixed up front, but are themselves a function of the realizations of the previous terms in the martingale $X_1,\ldots,X_{k-1}$?

For concreteness, consider the following coin flipping game. An adversary has $n$ coins, which he flips in sequence (represented by random variables $B_i$ taking values uniformly in $\{-1,1\}$). After observing the outcomes of $B_1,\ldots,B_{i-1}$ (but crucially, not $B_i$), he chooses a non-negative weight $c_i$. At the end of the $n$ coin flips, we compute the quantity: $$X_n = \sum_{i=1}^n c_i\cdot B_i$$

Can we now say that: $$\Pr\left[X_N \geq \sqrt{2\sum_kc_k^2 \ln(1/\delta)}\right] \leq \delta$$

noting that here, the values $c_k$ are now random variables themselves?

There is no such inequality even if we further restrict $c_k$ to be in $\{0,1\}$ and weaken the inequality to include a constant factor. (I think it is natural to add the condition that the $c_k$ values are uniformly bounded.) Suppose $c_k \in \{0,1\}$ and without loss of generality no $1$ follows a $0$. The choice of $c_k$ is equivalent to a stopping rule $\tau \le N$. We bet a constant amount on each toss of a coin and decide to stop after $\tau$ flips: $c_k = 0$ when $k \gt \tau$, so $c_k$ only depends on $X_1,...,X_{k-1}$.

Choose a constant $s \gt 0$. Can we bound

$$P\left(X_N \ge s \sqrt{\sum_{k=1}^N c_k^2}\right) = P(X_\tau \ge s \sqrt{\tau})?$$

The law of the iterated logarithm implies that for an infinite sequence $\{B_i\}$, the maximum number of standard deviations of $\sum B_i$ above the mean is almost surely unbounded, hence as $N\to \infty$ the maximum exceeds $s$ with probability approaching $1$. We can let $\tau$ be the minimum of $N$ and the first time $t$ so that $\sum_{i=1}^{t} B_i > s\sqrt{t}$.

If you let the bound depend on $N$, something like

$$P(\max \frac{X_t}{\sqrt{t}} \ge s) \le f(s,N),$$

then there are nontrivial bounds possible.

• Excellent example. Can you elaborate on your last point? In the special case of choosing a stopping rule, it seems we can give the bound: $\Pr[X_{\tau} \geq s\sqrt{\tau \log n/\delta}] \leq \delta$. Might a similar bound be possible in the general case -- i.e. $\Pr[X_n \geq s\cdot \sqrt{\sum_k c_k^2 \log n/\delta}] \leq \delta$ ? – Aaron Jan 3 '16 at 21:36
• Can you rewrite this answer in a more formal way? It is difficult for me to follow. In particular, what is the upper limit of the summation in the definition of $\tau$? What is the definition of $c_k$? If $\tau=N\wedge\min\{k\colon\sum_1^k B_i>s\}$ (I guess you meant $s\sqrt k$ here in place of $s$) and $c_k=I\{k\le\tau\}$, then $c_k$ will depend on $B_k$, which was not allowed in the question. – Iosif Pinelis Jan 3 '16 at 22:40
• @Iosif Pinelis: If the first time $t$ so that $X_t \gt s\sqrt{t}$ is $t=5$, then we say $\tau=5$. This sets $c_6=0$, not $c_5=0$. The weight $c_k$ only depends on $B_1,...B_{k-1}$. The fenceposting isn't the point. The point is that you can choose to stop at any number of standard deviations away from the mean with high probability, a weak corollary of the law of the iterated logarithm. Is that part unclear? – Douglas Zare Jan 4 '16 at 0:17
• Douglas: On another thought, I see now that your $c_k$ depends only on $B_1,\dots,B_{k-1}$, since $c_k=1-I\{\tau\le k-1\}$ -- if indeed $c_k=I\{k\le\tau\}$ is your definition of $c_k$. My problem was to understand, not the law of the iterated logarithm or its consequences, but mainly what your definitions of $\tau$ and $c_k$ were. – Iosif Pinelis Jan 4 '16 at 1:31
• @Aaron: I'm not sure what the right bounds are that depend on $N$. To get good bounds, I think you want an effective version of the law of the iterated logarithm. I've seen an effective version on one side for a simple $\pm 1$ random walk but not both sides in general, so I would have to go back to the proof of the law of the iterated logarithm to try to make that effective. – Douglas Zare Jan 4 '16 at 16:02

This inequality cannot be true. Let us rewrite it in the more common form $$P(R_n\ge x)\le e^{-x^2/2} \tag{1}$$ for $x\ge0$, where $R_n:=S_n/b_n$, $S_n:=\sum_1^n c_iB_i$, $b_n:=\sqrt{\sum_1^n c_i^2}$.

Let $n=2$, $c_1=1$, and $c_2=aI\{B_1=-1\}$, where $I\{\cdot\}$ denotes the indicator function, $a>0$ is large enough so that $\frac{-1+a}{\sqrt{1+a^2}}>x$, $x$ is less than $1$ but close enough to $1$ so that $e^{-x^2/2}<0.7$ (note that $e^{-1^2/2}=0.606\ldots<0.7$). Then $$P(R_2\ge x)=P(R_2\ge x,B_1=1)+P(R_2\ge x,B_1=-1)$$ $$=P(R_1\ge x,B_1=1)+P\Big(\frac{-1+aB_2}{\sqrt{1+a^2}}\ge x,B_1=-1\Big)$$ $$=P(B_1\ge x,B_1=1)+P(B_2=1,B_1=-1)$$ $$=P(B_1=1)+P(B_2=1,B_1=-1)$$ $$=\tfrac12+\tfrac14=0.75>0.7>e^{-x^2/2},$$ so that $(1)$ fails to hold.

Letting now $c_3=\dots=c_n=0$, one disproves the inequality in question for any natural $n\ge2$.

(What is sometimes referred to as the Azuma (or Hoeffding--Azuma) inequality is due entirely to [Hoeffding 1963]; see the last paragraph of Section 2 there.)

Addendum: I doubt very much that any modification of the inequality in question can hold without preventing the sum of the conditional variances of the increments of the martingale from being too small; cf. e.g. inequalities (1.11) in [de la Peña]. That actually gave me the idea for the counterexample.

• Thanks -- this is a nice counter-example, which shows that the inequality fails to hold in the adaptive setting, at least with the same constants. Do you know whether it is possible to get similar asymptotic concentration in this setting? i.e. a bound as in the question, but with different constants? Any non-trivial concentration at all, as a function of the realized $c_1,\ldots,c_n$? – Aaron Jan 3 '16 at 20:30