Does Multiplicative Version of Azuma's Inequality Hold? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T09:27:09Z http://mathoverflow.net/feeds/question/119584 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119584/does-multiplicative-version-of-azumas-inequality-hold Does Multiplicative Version of Azuma's Inequality Hold? Liwei Wang 2013-01-22T17:15:42Z 2013-01-22T17:15:42Z <p>It is known that there are multiplicative version concentration inequalities for sums of independent random variables. For example, the following multiplicative version <strong>Chernoff</strong> bound.</p> <hr> <p><strong>Chernoff bound:</strong></p> <p>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$,</p> <p>$\Pr\left(Y \ge (1+\delta)EY \right) \le e^{-c\cdot(EY)\delta ^2},$</p> <p>where $c$ is some absolute constant, e.g., c=1/248.</p> <hr> <p>Now consider <strong>dependent</strong> random variables. A slight variant of <strong>Azuma</strong>'s inequality states the following.</p> <hr> <p><strong>Azuma's Inequality:</strong></p> <p>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$,</p> <p>$\Pr\left(Y \ge m+\lambda \right) \le e^{-2 \lambda^2/n}.$</p> <hr> <p>Azuma's inequality is additive. My question is that does a multiplicative version of Azuma's inequality such as the following hold?</p> <hr> <p><strong>My question:</strong> does the following hold?</p> <p>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$</p> <p>$\Pr\left(Y \ge (1+\delta)m \right) \le e^{-c\cdot m \delta^2},$</p> <p>where $c$ is some absolute constant.</p> <hr> <p><strong>Note</strong>: the standard Azuma's inequality does not imply the multiplicative version when $m \ll \sqrt{n}$.</p>