Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.