Does Multiplicative Version of Azuma's Inequality Hold?

Question

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

Answer 1

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

Answer 2

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