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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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