Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
1  
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
show 1 more comment

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.