6
$\begingroup$

We know 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 $X=\sum_{i=1}^n X_i$. Then for any $\delta>0$,

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

where $c$ is some absolute constant.


Now we 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_{<i}] \le m\right) = 1.$ Let $X=\sum_{i=1}^n X_i$. Then for any $\lambda > 0$,

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


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


My question:

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_{<i}] \le m\right) = 1.$ Let $X=\sum_{i=1}^n X_i$. Then for any $\delta >0$

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

where $c$ is some absolute constant.


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

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.