# Concentration inequalities for gaussian variables

How would you prove this?

$$\mathbb{P}\left[\left|\frac{1}{n}\sum_{i=1}^{n}x_i-\mu\right| \leq \sigma\sqrt\frac{2\log(2\delta)} {n}\right]\geq 1 - \delta$$

Assuming that $x_1...x_n$ are independent Gaussian RVs with mean $\mu$ and variance $\sigma^2$

• I think there's a mistake in your formula. As it stands, $\delta$ could be quite close to $0$ which would lead to $\log(2\delta)$ being negative. – jld Apr 28 '17 at 18:44
• First reduce it to a statement about the standard Normal variable $X=\frac{1}{\sigma}\left(\frac{1}{n}\sum x_i - \mu\right)$, thereby eliminating all appearances of $n, \mu,$ and $\sigma$. That should make it obvious that the assertion is false even for meaningful values of $\delta$: plugging in $\delta=1/2$, for instance, produces the assertion $\Pr(|X|\le 0) \ge 1/2$. – whuber Apr 28 '17 at 18:44
• The simple bound $Q(x)< \frac 12\exp(-x^2/2)$ for $x>0$ should suffice to prove a more reasonable version of what you want to prove. – Dilip Sarwate Apr 28 '17 at 19:04

You've got a random variable $\bar X_n \sim \mathcal N(\mu, \sigma^2/n)$ and you're looking to quantify the probability that $\bar X_n$ is a certain distance from its mean. This means you'll want to make use of a concentration inequality.

I'm going to prove a result that is very similar to your question but with some modifications so that it is actually true. I will show that $$\mathbb P\left( \big\vert \bar X_n - \mu \big\vert > \sigma \sqrt{\frac{-4\log(\delta / \sqrt 2)}{n}} \right) < \delta$$ for $0 < \delta < 1$.

We know that $\bar X_n - \mu \sim \mathcal N(0, \sigma^2/n)$ so $\frac{n}{\sigma^2}|\bar X_n - \mu | ^2 \sim \chi^2_1$ If $Y \sim \chi^2_\nu$ then the MGF of $Y$ is $$M_Y(t) = E(e^{tY}) = (1-2t)^{-\nu/2}.$$ Now by Chernoff's bound we have $$\mathbb P\left( \frac{n}{\sigma^2} \big\vert \bar X_n - \mu \big\vert^2 > \log \left(4 \delta^{-4}\right) \right) < \frac{(1-2t)^{-1/2}}{(4 \delta^{-4})^t} = \delta$$ if we let $t = \frac 14$.

• I think that that $\log(4\delta^{-4})$ in the last displayed equation should be $\displaystyle\sqrt{\log(4\delta^{-4})}$, maybe? Also, could you provide a link to where you got the specific form of Chernoff bound for the $\chi^2$ random variable? I am more used to seeing it in the form $$P\{X > x\} < \min_{\lambda >0} e^{-\lambda x}M_X(\lambda).$$ – Dilip Sarwate Apr 29 '17 at 15:13
• @DilipSarwate I don't think there's a missing square root -- I start off with $\sqrt{-4 \log (\delta / \sqrt 2)}$ and then square both sides. And I'm using the form of Chernoff's bound given here: en.wikipedia.org/wiki/Concentration_inequality#Chernoff_bounds – jld Apr 30 '17 at 20:37
• OK, I understand why there is no missing square root (you are working with $P(Z^2 > z^2)$ instead of $P(|Z| > z)$), but I am still puzzled as to where that $4\delta^{-4}$ came from and whether $t=\frac 14$ does indeed give the minimum value of the Chernoff bound. – Dilip Sarwate May 2 '17 at 3:03

Let $X$ denote a standard normal random variable. As the comments and Chaconne's answer have noted, the question here is to bound $P\{|X| > x\} = 2Q(x)$ where $Q(x) = 1 - \Phi(x)$ is the complementary normal distribution function. Now, a well-known bound is $$Q(x) < \frac 12e^{-x^2/2} ~~ \text{for } x > 0 \tag{1}$$ which immediately gives $$P\{|X| > x\} < e^{-x^2/2}, \tag{2}$$ or, writing $\delta$ for the right side of $(2)$, $$P\left\{|X| > \sqrt{-2\ln(\delta)}\right\} < \delta \tag{3}$$ Note that this is different from @Chaconne's result $\displaystyle P\left\{|X| > \sqrt{-4 \ln (\delta/\sqrt{2})}\right\} < \delta$.

Proof of $(1)$: Let $Y \sim N(0,1)$ be independent of $X$. Then, for $x>0$, $$P\{|X| > x, |Y| > x\} = 4[Q(x)]^2 < P\{X^2+Y^2 > 2x^2\}.$$ But $X^2+Y^2$ is an exponential random variable with parameter $\frac 12$ and so $$P\{X^2+Y^2 > 2x^2\} = e^{-\frac 12\cdot 2x^2} = e^{-x^2}\implies Q(x) < \frac 12e^{-x^2/2}.$$

Chernoff bound on $Q(x)$: For every choice of $\lambda > 0$, $\mathbf 1_{\{t\colon t > x \}} < e^{\lambda (t-x)}$ and so $$P\{X > x\} = E[\mathbf 1_{\{X\colon X > x \}}] < E[e^{\lambda (X-x)}] = e^{-\lambda x}E[e^{\lambda X}] = e^{-\lambda x}\cdot e^{\lambda^2/2}$$ leading to $$P\{X > x\} \leq \min_{\lambda >0}\exp\left(\frac{\lambda^2}{2} - x \lambda\right) = e^{-x^2/2}$$ since the minimum occurs at $\lambda = x$. This gives $$P\left\{|X| > \sqrt{-2\ln (\delta/2)}\right\} < \delta. \tag{4}$$ This is weaker than $(3)$ but it too is different from Chaconne's result.