7
$\begingroup$

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/3.


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 $\mu$, such that $ \Pr \left( \sum_{i=1}^n \mathbb{E}[X_i|X_{1},\ldots,X_{i-1}] \le \mu\right) = 1$. Let $Y=\sum_{i=1}^n X_i$. Then for any $\lambda > 0$,

$\Pr\left(Y \ge n\mu+\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 $\mu$, such that $\Pr\left( \sum_{i=1}^n \mathbb{E}[X_i|X_1,\ldots,X_{i-1}] \le \mu\right) = 1.$ Let $Y=\sum_{i=1}^n X_i$. Then for any $\delta>0$

$\Pr\left(Y \ge (1+\delta)n\mu \right) \le e^{-c\cdot n\mu \delta^2},$

where $c$ is some absolute constant.


Note: the standard Azuma's inequality does not imply the multiplicative version when $n\mu \ll \sqrt{n}$.

$\endgroup$
  • $\begingroup$ Something is broken. Maybe you want $Y$ to be the mean of $X_1,\ldots,X_n$ instead of the sum? $\endgroup$ – Brendan McKay Jan 22 '13 at 23:56
  • $\begingroup$ Are you only interested in the case of small $\delta$? You statement of Chernoff does not seem right to me for large $\delta$. $\endgroup$ – Ori Gurel-Gurevich Jan 23 '13 at 1:12
  • 1
    $\begingroup$ Also, take a look at arxiv.org/abs/0901.4056, section 2, particularly proposition 2.3, and see if that helps. $\endgroup$ – Ori Gurel-Gurevich Jan 23 '13 at 1:15
  • $\begingroup$ 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.? $\endgroup$ – Liwei Wang Jan 23 '13 at 16:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Ori Gurel-Gurevich Jan 23 '13 at 22:45
2
$\begingroup$

Yes, such bounds are possible. You can adapt the proof of Azuma's inequality to the multiplicative-error case, if you set it up correctly. For example:

Lemma 10 [this paper]. Let $Y=\sum_{t=1}^T x_t$ and $Z=\sum_{t=1}^T z_t$ be sums of non-negative random variables, where $T$ is a random stopping time with finite expectation, and, for all $t$, $|x_t-z_t|\le 1$ and $$\textstyle E\big[\,x_{t} - z_{t} ~|\, \sum_{s< t} x_s, \sum_{s< t} z_s\,\big] ~\le~ 0.$$ Let $\epsilon\in[0,1]$ and $A\in\mathbb{R}$. Then $$\Pr\big[\,(1-\epsilon) Y \,\ge\, Z + A\, \big] ~\le~ \exp({-\epsilon}A).$$


To apply this to your question, take $T=n$, $z_t=\mu$, and $A=\epsilon\, n\, \mu$. Then you get $$\Pr\big[\,Y \,\ge\, \frac{1+\epsilon}{1-\epsilon}n\mu\, \big] ~\le~ \exp({-\epsilon^2}n\mu).$$

$\endgroup$
  • $\begingroup$ I should add that for your question you should be able to adapt the proof of Chernoff (with bound $\exp(-\epsilon^2 n \mu/3)$) directly to show that same bound. For example, define $$\phi_t = \frac{\prod_{i=1}^t (1+\epsilon x_i) \times \exp(-\epsilon \mu (n-t))}{(1+\epsilon)^{(1+\epsilon)\mu n}}.$$ Then $\phi_0, \phi_1, \ldots, \phi_n$ is a super-martingale, so $E[\phi_n] \le \phi_0$. From this inequality the desired bound follows as in the proof of standard Chernoff. $\endgroup$ – Neal Sep 14 '17 at 15:16
2
$\begingroup$

$\newcommand{\de}{\delta}$ The "dependent" version of the multiplicative Chernoff bound can be proved quite similarly to the "independent" case. Indeed, let $E_{i-1}$ denote the conditional expectation given $X_1,\dots,X_{i-1}$, so that $E_{i-1}X_i\le\mu$ almost surely (a.s.) for $i=1,\dots,n$. Take any real $t\ge0$. By the convexity of $e^{tx}$ in $x$ and the conditions that $0\le X_i\le1$ and $E_{i-1}X_i\le\mu$, we have $e^{tX_i}\le1+(e^t-1)X_i$ and hence \begin{equation*} E_{i-1}e^{tX_i}\le1+(e^t-1)E_{i-1}X_i\le1+(e^t-1)\mu\le\exp\{(e^t-1)\mu\} \end{equation*} for $i=1,\dots,n$. So, by induction, for $j=1,\dots,n$ and $Y_j:=\sum_1^j X_i$ we have \begin{equation*} Ee^{tY_j}=EE_{j-1}e^{tY_j}=Ee^{tY_{j-1}}E_{j-1}e^{tX_j}\le Ee^{tY_{j-1}}\exp\{(e^t-1)\mu\}, \end{equation*} whence, by induction, \begin{equation*} Ee^{tY}=Ee^{tY_n}\le\exp\{n(e^t-1)\mu\}. \end{equation*} So, using Markov's inequality and then choosing $t=\ln(1+\de)$, we get \begin{align*} P(Y\ge(1+\de)n\mu)&\le e^{-(1+\de)n\mu t}Ee^{tY} \le\exp\{-(1+\de)n\mu t+n(e^t-1)\mu\} \\ &=\exp\{-n\mu\psi(\de)\}, \end{align*} where $\psi(u):=u-(1+u)\ln(1+u)$. Up to notation, this bound is the same as the known multiplicative Chernoff bound in the "independent" case.

Since $\psi(u)\le-u^2/3$ for $u\in[0,3/2]$, we have \begin{equation*} P(Y\ge(1+\de)n\mu)\le\exp\{-n\mu\de^2/3\} \tag{1} \end{equation*} if $\de\in[0,3/2]$.

Note that (1) cannot hold for all $\de\ge0$, even in the "independent" case. Indeed, suppose that the $X_i$'s are iid with $P(X_1=1)=\mu=1-P(X_i=0)$, where $\mu:=1/n$ and $n\to\infty$. Then $Y$ will converge in distribution to a random variable $\Pi$ with the Poisson distribution with parameter $1$, and (1) will yield \begin{equation*} P(\Pi\ge1+\de)\le\exp\{-\de^2/3\}. \end{equation*} Since Poisson distributions are not subgaussian, the latter inequality cannot hold for all $\de\ge0$. So, (1) cannot hold for all $\de\ge0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.