# Does Multiplicative Version of Azuma's Inequality Hold?

It is known that there are multiplicative version concentration inequalities for sums of independent random variables. For example, the following multiplicative version Chernoff bound.

Chernoff bound:

Let $X_1,\ldots,X_n$ be independent random variables and $X_i \in$ $[0,1]$. Let $Y=\sum_{i=1}^n X_i$. Then for any $\delta>0$,

$\Pr\left(Y \ge (1+\delta)EY \right) \le e^{-c\cdot(EY)\delta ^2},$

where $c$ is some absolute constant, e.g., c=1/248.

Now consider dependent random variables. A slight variant of Azuma's inequality states the following.

Azuma's Inequality:

Let $X_1,\ldots,X_n$ be (dependent) random variables and $X_i \in [0,1]$. Assume that there exists $m$, such that $\Pr \left( \sum_{i=1}^n \mathbb{E}[X_i|X_{1},\ldots,X_{i-1}] \le m\right) = 1$. Let $Y=\sum_{i=1}^n X_i$. Then for any $\lambda > 0$,

$\Pr\left(Y \ge m+\lambda \right) \le e^{-2 \lambda^2/n}.$

Azuma's inequality is additive. My question is that does a multiplicative version of Azuma's inequality such as the following hold?

My question: does the following hold?

Let $X_1,\ldots,X_n$ be (dependent) random variables and $X_i \in [0,1]$. Assume that there exists $m$, such that $\Pr\left( \sum_{i=1}^n \mathbb{E}[X_i|X_1,\ldots,X_{i-1}] \le m\right) = 1.$ Let $Y=\sum_{i=1}^n X_i$. Then for any $\delta>0$

$\Pr\left(Y \ge (1+\delta)m \right) \le e^{-c\cdot m \delta^2},$

where $c$ is some absolute constant.

Note: the standard Azuma's inequality does not imply the multiplicative version when $m \ll \sqrt{n}$.

-
Something is broken. Maybe you want $Y$ to be the mean of $X_1,\ldots,X_n$ instead of the sum? – Brendan McKay Jan 22 '13 at 23:56
Are you only interested in the case of small $\delta$? You statement of Chernoff does not seem right to me for large $\delta$. – Ori Gurel-Gurevich Jan 23 '13 at 1:12
Also, take a look at arxiv.org/abs/0901.4056, section 2, particularly proposition 2.3, and see if that helps. – Ori Gurel-Gurevich Jan 23 '13 at 1:15
Ori, Thanks a lot! Your result is very relavant to my question. On the one hand, the proposition in your paper is stronger than my question; it's a uniform bound over n. But on the other hand, your result does not directly give an affirmative answer to my question. Using the notion in your paper, if m is an upper bound of $\sum_{i=1}^t Y_i$, can I say $\sum_{i=1}^t X_i < 3m/2$ w.h.p.? – Liwei Wang Jan 23 '13 at 16:22
If by w.h.p. you mean a bound going to 0 with $m$, then I think the answer is yes. Just add more $X_i$ at the end that will make sure that $\sum Y_i$ is equal to $m$ and then apply proposition 2.3. – Ori Gurel-Gurevich Jan 23 '13 at 22:45