2
$\begingroup$

I'm trying to derive the Chernoff bound $\mathrm{erfc}(x) \le \exp(-x^2)$, by first showing:

$$\mathrm{erfc}(x) = \frac{2}{\pi}\int_{0}^{\frac{\pi}{2}}\exp\left(-\frac{x^2}{\cos^2\theta}\right)d\theta$$

This equality should be derived by considering 2 independent, standard gaussian random variables $x_1, x_2$ and the region in the $x_1x_2$-plane where $|x_1|\le x$.

What I have so far, is come up with a diagram like this:

enter image description here

where I consider the the probability where $x_1, x_2$ falls in the square (4 $\times$ "blue square"). Then

\begin{align} P(x_1<x,x_2<x) &= P(x_1<x)P(x_2<x)\\ &=\frac{1}{2\pi}\int_{0}^{x}\int_{0}^{x}e^{-\frac{x_1^2+x_2^2}{2}}dx_1dx_2\\ &=\frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}\int_{0}^{\frac{x}{\cos\theta}}e^{-\frac{r^2}{2}}rdrd\theta\\ &=\frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}\int_{0}^{\frac{x^2}{2\cos^2\theta}}e^{-v}dvd\theta\\ &=\frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}-e^{-v}\Big|_0^{\frac{x^2}{2\cos^2\theta}}d\theta\\ &=\frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}1-e^{-\frac{x^2}{2\cos^2\theta}}d\theta\\ &=\frac{1}{4} - \frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}e^{-\frac{x^2}{2\cos^2\theta}}d\theta \end{align} This is the probability for the blue square, so for the entire square, I have: \begin{align} 4P(x_1<x,x_2<x)&=1-\frac{2}{\pi}\int_{0}^{\frac{\pi}{2}}e^{-\frac{x^2}{2\cos^2\theta}}d\theta \end{align} The probability of falling outside the square is: $$1-\Big[1-\frac{2}{\pi}\int_{0}^{\frac{\pi}{2}}e^{-\frac{x^2}{2\cos^2\theta}}d\theta\Big] = \frac{2}{\pi}\int_{0}^{\frac{\pi}{2}}e^{-\frac{x^2}{2\cos^2\theta}}d\theta$$

I'm kind of stuck here. I think this is my $[Q(x)]^2$, but according to this paper (Eq 9), my $Q(x)$ is incorrect. How can I derive the $Q$-function in the paper using this gaussian RV derivation method?

ETA: As per Dilip Sarwate's suggestion, I considered the circle that circumscribes the squares, and I got the following by considering just 1 (upper-right) quadrant.

\begin{align} P(\text{in the circle quadrant}) &= \frac{1}{2\pi}\int_{0}^{\sqrt{2}x}\int_{0}^{\sqrt{2x^2-x_2^2}}e^{-\frac{x_1^2+x_2^2}{2}}dx_1dx_2\\ &=\frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}\int_{0}^{\sqrt{2}x}e^{-\frac{r^2}{2}}rdrd\theta\\ &=\frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}\int_{0}^{x^2}e^{-v}dvd\theta\\ &=\frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}-e^{-v}\Big|_0^{x^2}d\theta\\ &=\frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}1-e^{-x^2}d\theta\\ &=\frac{1}{4}-\frac{1}{4}e^{-x^2} \end{align}

\begin{align} \text{P(in the blue square)} &< \text{P(in the circle quadrant)}\\ \frac{1}{4} - \frac{1}{2\pi}\int_{0}^{\frac{\pi}{2}}e^{-\frac{x^2}{2\cos^2\theta}}d\theta &< \frac{1}{4}-\frac{1}{4}e^{-x^2}\\ \frac{2}{\pi}\int_{0}^{\frac{\pi}{2}}e^{-\frac{x^2}{2\cos^2\theta}}d\theta &> e^{-x^2} \end{align} Let $v = \frac{x}{\sqrt{2}}$

\begin{align} \frac{2}{\pi}\int_{0}^{\frac{\pi}{2}}e^{-\frac{v^2}{cos^2\theta}}d\theta &> e^{-2v^2} \end{align} I still don't quite understand how my lefthand expression became erfc(v), since it was calculated from $P(x_1<x,x_2<x)$, and how to eventually get $\mathrm{erfc}(x) \le \exp(-x^2)$.

$\endgroup$
  • 1
    $\begingroup$ Hint: you are looking for a bound and not the exact value. Find the probability of being inside the circle that circumscribes the 4 squares. $\endgroup$ – Dilip Sarwate Mar 13 '16 at 14:13
  • $\begingroup$ @DilipSarwate I have added my calculations on the probability of being in the circle to my OP, as you have hinted. But I'm still not quite there yet... $\endgroup$ – Rayne Mar 14 '16 at 7:17
2
$\begingroup$

I don't know why you are approaching the problem the way you are by going to a two-dimensional approach.

The Chernoff bound starts with the observation that for any random variable $X$ and any $\lambda > 0$, $$P\{X \geq a\} \leq E[\exp(\lambda(X-a))]\tag{1}$$ because $\exp(\lambda(x-a))\geq \mathbf 1_{\{x\colon x \geq a\}}$. Consequently, $$P\{X \geq a\} \leq \min_{\lambda > 0}E[\exp(\lambda(X-a))].\tag{2}$$ For a standard Gaussian random variable, $E[\exp(\lambda(X-a))]$ can be found easily by using a method called "completing the square" (in the exponent which as terms like $-\frac{1}{2}x^2+\lambda(x-a)$ in it) and noting that the resulting integral is the integral of a Gaussian density times a constant. Alternatively, you can use the moment-generating function and read off the answer. After minimization with respect to $\lambda$, the result is $$P\{X \geq a\} = Q(x) \leq e^{-\frac{x^2}{2}}.\tag{3}$$ The two-dimensional approach leads to the slightly better result $$Q(x) \leq \frac 12e^{-\frac{x^2}{2}}.\tag{4}$$ Note that you have proved already that for $x > 0$, $$P\{X_1>x, X_2>x\} = Q^2(x) \leq \frac 14 e^{-{x^2}}$$ from which $(4)$ follows immediately, and $(4)$ is not the Chernoff bound on $Q(x)$.

$\endgroup$

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.