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$
 A: 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$.
A: 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.
