bounded difference inequalities

These are concentration inequalities that concern functions of random variables that obey a bounded differences condition. Intuitively this means that if you change one argument, the function value doesn’t change too much.

The most famous example of a bounded difference inequality is McDiarmid’s inequality, which is the following. Suppose $f:{\mathbb{R}}^n\to \mathbb{R}$ obeys

$$\underset{z_1,\dots ,z_n,z_i^{\prime }}{\sup }|f(z_{-i},z_i)-f(z_{-i},z_i^{\prime })|\le c_i,$$

for all $i$. (Here $z_{-i}$ is the vector of arguments that omits $z_i$). Then

$$\mathbb{P}(|f(X^n)-\mathbb{E}[f(X^n)]|\ge ϵ)\le 2\exp \left(-\frac{2{ϵ}^2}{{\sum }_{i=1}^n{c}_i^2}\right).$$

Note this is a generalization of the Hoeffding’s bound. It is recovered by taking $f(x^n)=\frac{1}{n}{\sum }_{i=1}^n{x}_i$.

In fact, $f$ need not be a function with domain ${\mathbb{R}}^n$. We can replace ${\mathbb{R}}^n$ with ${\mathcal{X}}^n$ for any space $\mathcal{X}$. (See Raginsky’s lecture notes for the proof). This is useful if, for instance, we are interested in obtaining bounds on the norm of random vectors. If we take $\mathcal{X}={\mathbb{R}}^n$ for instance, then $f$ could be $f=\left|{\sum }_i{X}_i\right|$ and we can obtain deviation inequalities between $\left|{\sum }_i{X}_i\right|$ and $\mathbb{E}\left|{\sum }_i{X}_i\right|$.