Bounds on the expected deviation of a sum from a threshold.

Here are bounds on the expected deviation of a sum of 0/1-random variables above or below some threshold (typically near its mean).

For example, suppose Alice flips a fair coin $n$ times. She pays Bob $1 for each head after the first $(1+\varepsilon )n/2$ heads (if any). What is her expected payment to Bob? The bounds here say: at most $\varepsilon ^{-1} \exp (-\varepsilon ^2 n/6)$ . For example, if $\varepsilon =\Omega (1/\sqrt n)$ , the expected payment is $O(\sqrt n)$ . If $\varepsilon =\sqrt{6c\ln (n)/n}$ , the expected payment is $O(1\, /\, n^{c-1}\sqrt{\ln n})$ . In general the expectation is about $\varepsilon ^{-1}$ times the probability (according to Chernoff) that the sum exceeds its mean by a factor of $1+\varepsilon$ .

Click for background material…

Sums with a fixed number of terms

First, bounds that are directly analogous to standard Chernoff bounds:

Lemma 1 (expected deviation from threshold).

Let $Y=\sum _{t=1}^T y_t$ be a sum of independent random variables, where each $y_t$ is in $[0,1]$ and $T\gt 0$ is fixed. Let $\varepsilon , \mu \gt 0$ with $\varepsilon \le 1$ .

(a) If $\textrm{E}[y_{t}] \le \mu$ for all $t\le T$ then $\textrm{E}[\max \{ 0, Y - (1+\varepsilon )\mu T\} ] \, \lt \, \varepsilon ^{-1}\, \exp ({-\varepsilon ^2}\mu T/3).$

(b) If $\textrm{E}[y_{t}] \ge \mu$ for all $t\le T$ then $\textrm{E}[\max \{ 0, (1-\varepsilon )\mu T - Y\} ] \, \lt \, \varepsilon ^{-1}\, \exp ({-\varepsilon ^2}\mu T/2).$

Proof of Lemma 1

Proof.

(a) Using¹ $\max \{ 0,z\} \le \varepsilon ^{-1} (1+\varepsilon )^z$ , then following the proof of the Chernoff bound, the expectation in question is at most

$\begin{equation} \label{eqn} \textrm{E}\left[\frac{\varepsilon ^{-1}\, (1+\varepsilon )^Y}{(1+\varepsilon )^{(1+\varepsilon )\mu T}}\right] ~ \le ~ \varepsilon ^{-1} \Big( \frac{e^{\varepsilon }}{(1+\varepsilon )^{1+\varepsilon }} \Big)^{\mu T} ~ \lt ~ \varepsilon ^{-1} \exp (-\varepsilon ^2 \mu T/3). \end{equation}$

(b) Using² $\max \{ 0,z\} \le \varepsilon ^{-1}(1-\varepsilon )^{-z}$ , then following the proof of the Chernoff bound, the expectation in question is at most

$\begin{equation} \label{eqn2} \textrm{E}\left[\frac{\varepsilon ^{-1}\, (1-\varepsilon )^Y}{(1-\varepsilon )^{(1-\varepsilon )\mu T}}\right] ~ \le ~ \varepsilon ^{-1} \Big( \frac{e^{-\varepsilon }}{(1-\varepsilon )^{1-\varepsilon }} \Big)^{\mu T} ~ \lt ~ \varepsilon ^{-1} \exp (-\varepsilon ^2 \mu T/2). \end{equation}$

Sums with randomly many terms

Assume a system goes through a random sequence of states $S_1,S_2,\ldots ,S_T$ , where each state $S_t$ determines two values: $x_t$ and $y_t$ , each in $[0,1]$ , where the expectation of each $x_t$ is at most that of $y_t$ :

$\textrm{E}[x_t \, |\, S_{t-1}]~ \le ~ \textrm{E}[y_t \, |\, S_{t-1}].$

Let $X_t=\sum _{i=1}^t x_i$ and $Y_t=\sum _{i=1}^t y_i$ .

Lemma 2 (expected deviation from threshold).

For any stopping time $T$ with finite expectation, and any $\varepsilon ,\mu \gt 0$ with $\varepsilon \le 1$ , if $X_t - Y_t$ is uniformly bounded from above (for all $t\lt T$ , by some finite bound independent of the outcome of the experiment), then the expectation of $\textstyle \max \big\{ \, 0, ~ X_T/(1+\varepsilon ) ~ -~ Y_T/(1-\varepsilon ) ~ -~ \varepsilon \mu \, \big\}$ is at most $\varepsilon ^{-1}\exp (-\varepsilon ^2\mu )$ .

Proof of Lemma 2

Proof.

The proof is similar to that of Lemma 1, but following the proof of stopping-time Chernoff, instead of the proof of Chernoff.

Using³ $\max \{ 0,a-b-c\} \le \varepsilon ^{-1}(1+\varepsilon )^{(1+\varepsilon )a}(1-\varepsilon )^{(1-\varepsilon )b}e^{-\varepsilon c}$ for $a,b,c\ge 0$ , the expectation in question is at most $\textrm{E}[\phi _T]$ where

$\begin{equation} \label{eqn3} \phi _t = \varepsilon ^{-1}\, (1+\varepsilon )^{X_t}(1-\varepsilon )^{Y_t} e^{-\varepsilon ^2\mu }. \end{equation}$

To finish, note that $\phi$ is a super-martingale, and $\phi _t$ is uniformly bounded from below (by 0) and from above (as $(1+\varepsilon )^{X_t}(1-\varepsilon )^{Y_t} \le \exp (\varepsilon (X_t-Y_t))$ and $X_t-Y_t$ is uniformly bounded from above). Hence, by Walds, the expectation of $\phi _T$ is at most $\phi _0 = \varepsilon ^{-1}\exp (-\varepsilon ^2\mu )$ .

Expected maximum deviation among many sums

Footnotes

$~ z\le e^{z-1}$ $\Rightarrow ~ \alpha z \le e^{\alpha z}/e$ $\Rightarrow ~ z \le e^{\alpha z} / e\alpha$ $\Rightarrow ~ z \le (1+\varepsilon )^z / e\ln (1+\varepsilon )$ $\Rightarrow ~ z \le (1+\varepsilon )^z / \varepsilon$ .
WLOG $z\ge 0$ . That and $1+\varepsilon \lt 1/(1-\varepsilon )$ and $z\le (1+\varepsilon )^z/\varepsilon$ imply $z \le (1+\varepsilon )^z / \varepsilon \lt (1-\varepsilon )^{-z}/\varepsilon$ .
Using $(1+\varepsilon )^{1+\varepsilon }(1-\varepsilon )^{1-\varepsilon } \ge 1$ and $(1+\varepsilon )^{1+\varepsilon }e^{-\varepsilon } \ge 1$ , reduce to case $a=0$ (trivial) or $b=c=0$ (follows from previous).

Notes on algorithms

Lecture notes on algorithms

Expected deviation of a sum

Sums with a fixed number of terms

Proof of Lemma 1

Sums with randomly many terms

Proof of Lemma 2

Related

Footnotes