03 Bounds on deviation probability

Aka concentration of measure inequalities.

Expectation based deviation bound

(Aka Markov’s inequality). If $X\ge 0$: $Pr(X\ge a)\le \frac{E[X]}{a}$: $Pr(X\ge a)$ is max when $X$ is 0 or a.

Averaging argument. If $X\le k$, $c\mu Pr(X\le c\mu )+k(1-Pr(X\le c\mu ))\ge \mu$; so $Pr(X\le c\mu )\le \frac{k-\mu }{k-c\mu }$.

This technique is used repeatedly in other deviation bounds based on variance and moment generating functions.

Variance based deviation bound

(Aka Chebyshev’s inequality). By Markov’s inequality: $Pr((X-E[X]{)}^2\ge a^2)\le \frac{Var[X]}{a^2}$.

Use in estimation of mean

$Pr(n^{-1}(\sum X_i-E[X_i]{)}^2\ge a^2)=Pr((\sum X_i-E[X_i]{)}^2\ge n{a}^2)\le \frac{Var[\sum X_i]}{n{a}^2}$. Applicable for pair-wise independent Bernoulli trials.

Exponentially small deviation bounds

General technique

(Chernoff) $Pr(e^{tX}\ge e^{ta})\le E[e^{tX}]/e^{ta}$: applying Markov. Used to bound both $Pr(X>a)$ and $Pr(X<a)$ with $t>0$ or $t<0$. Get a bound exponentially small in $\mu$, deviation.

For random variable sequences

$\mu =\sum E[X_i]$. For $X=\sum _{i=1}^n{X}_i$. Note that RVs are not necessarily identically distributed.

Pairwise independent RVs

Use variance based deviation bounds, as variance of pairwise independent RVs is an additive function.

Sum of n-wise independent RVs

Bounds from MGF’s.

$Pr(e^{tX}\ge e^{ta})\le E[e^{tX}]/e^{ta}=(\prod E[e^{t{X}_i}])/e^{ta}$: here ye have used independence.

If $d>0$, $Pr(X\ge (1+d)\mu )\le \frac{e^{\mu (e^t-1)}}{e^{t(1+d)\mu }}\le \frac{e^{d\mu }}{(1+d{)}^{(1+d)\mu }}$: using $t=\ln (1+d)$ and $M_X$ bound.

So, if $R=(1+d)\mu >6\mu :d=\frac{R}{\mu }-1\ge 5,Pr(X\ge (1+d)\mu )\le (\frac{e}{6}{)}^R\le 2^{-R}$.

If d in (0,1], $Pr(X\ge (1+d)\mu )\le e^{\frac{-\mu d^2}{3}}$: As $\frac{e^d}{(1+d{)}^{(1+d)}}\le 2^{\frac{-d^2}{3}}$: as $f(d)=d-(1+d)\ln (1+d)+\frac{d^2}{3}\le 0$: as $f(0)\le 0$ and $f^{\prime }(d)<0$.

If d in (0,1], $Pr(X\le (1-d)\mu )<\frac{e^{-d\mu }}{(1-d{)}^{(1-d)\mu }}$; $Pr\le e^{\frac{-\mu d^2}{2}}$.

So, $Pr(|X-\mu |\ge d\mu )\le 2e^{-\mu d^2/3}$. \exclaim{So, probability of deviation from mean decreases exponentially with deviation from mean.}

Can be used in both additive and multiplicative forms.

Goodness of empirical mean

Now, $E[X_i]=p$. Using $X/n=\sum X_i/n$ to estimate mean p. So, $Pr(|\frac{\sum X_i}{n}-p|\ge dp)\le 2e^{-np{d}^2/3}$. \exclaim{So, probability of erroneous estimate decreasing exponentially with number of samples!}

Code length divergence bound

Let $D_p$ and $D_q$ be probability distributions of binary random variables with probabilities $p$ and $q$ of being 1 respectively.

$D_p(\sum _i{X}_i\ge qn)\le (n-qn)e^{-nKL(D_p||D_q)}$.

\pf{Suppose that $X_i\sim D_p$ and that $p<q,k\ge qn$.

$$D_p(\sum _i{X}_i=k)\le \frac{D_p(\sum _i{X}_i=k)}{D_q(\sum _i{X}_i=k)}=(\frac{p}{q}{)}^k(\frac{1-p}{1-q}{)}^{n-k}\le (\frac{p}{q}{)}^{qn}(\frac{1-p}{1-q}{)}^{n(1-q)}=e^{-nKL(D_p||D_q)}$$.

So, taking the union bound over all $k\ge qn$, we have the result.}

Using the connection between the code length divergence and the total variation distance: $KL(D_p||D_q)\ge 2(p-q{)}^2$. This can be used to derive other deviation bounds.

Additive deviation bounds

See Azuma inequality section.

iid RV: Tightness of the Chernoff bound

(Cramer) Take $l(a)=\underset{t}{max}ta-M(a)$. For large $n$: $Pr(\frac{\sum X_i}{n}\ge a)\ge e^{-n(l(a)+ϵ)}$ \why. Combining with Chernoff, $Pr(\frac{\sum X_i}{n}\ge a)=e^{-n(l(a)+{ϵ}_n)}$ for some seq $({ϵ}_n)\to 0$.

\part{Probabilistic Analysis Techniques}