# Derive chernoff bound for $\mathrm{erfc}(x)$

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:

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)$.

• 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. – Dilip Sarwate Mar 13 '16 at 14:13
• @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... – Rayne Mar 14 '16 at 7:17

## 1 Answer

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)$.