# Expected deviation of a sum

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 times. She pays Bob \$1 for each head after the first heads (if any). What is her expected payment to Bob? The bounds here say: at most . For example, if , the expected payment is . If , the expected payment is . In general the expectation is about times the probability (according to Chernoff) that the sum exceeds its mean by a factor of .

# Sums with a fixed number of terms

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

Lemma 1 (expected deviation from threshold).

Let be a sum of independent random variables, where each is in and is fixed. Let with .

(a) If for all then

(b) If for all then

# Proof of Lemma 1

Proof.

(a) Using1 , then following the proof of the Chernoff bound, the expectation in question is at most

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

(b) Using2 , then following the proof of the Chernoff bound, the expectation in question is at most

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

# Sums with randomly many terms

Assume a system goes through a random sequence of states , where each state determines two values: and , each in , where the expectation of each is at most that of :

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

Let and .

Lemma 2 (expected deviation from threshold).

For any stopping time with finite expectation, and any with , if is uniformly bounded from above (for all , by some finite bound independent of the outcome of the experiment), then the expectation of is at most .

# 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.

Using3 for , the expectation in question is at most where

$$\label{eqn3} \phi _ t = \varepsilon ^{-1}\, (1+\varepsilon )^{X_ t}(1-\varepsilon )^{Y_ t} e^{-\varepsilon ^2\mu }.$$

To finish, note that is a super-martingale, and is uniformly bounded from below (by 0) and from above (as and is uniformly bounded from above). Hence, by Walds, the expectation of is at most .

# Related

## Footnotes

1. .
2. WLOG . That and and imply .
3. Using and , reduce to case (trivial) or (follows from previous).