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$

  • $\begingroup$ 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. $\endgroup$ – jld Apr 28 '17 at 18:44
  • $\begingroup$ 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$. $\endgroup$ – whuber Apr 28 '17 at 18:44
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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).$$ $\endgroup$ – Dilip Sarwate Apr 29 '17 at 15:13
  • $\begingroup$ @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 $\endgroup$ – jld Apr 30 '17 at 20:37
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.