MathOverflow is a question and answer site for professional mathematicians. 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

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

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.