# Do subgaussian variables obey the slightly-stronger-than-Chernoff tail bound?

If $X \sim Normal(0,1)$, then we have the tail bound: $$(*) \qquad\Pr[X > t] \leq \mathcal{O}\left(\frac{e^{-t^2/2}}{t}\right) .$$

Now for general variables $X$, a nice condition is that $X$ be subgaussian, meaning that $\mathbb{E}[e^{tX}] \leq e^{t^2/2}$. In this case we traditionally get the tail bound $$\Pr[X > t] \leq e^{-t^2/2} .$$

My question is, can we actually get the tail bound of the form $(*)$, or is there a counterexample? I ask because it seems intuitively plausible, but I have never seen such a result in references such as Boucheron, Lugosi, and Massart.

(Edit) After some helpful answers I want to clarify: first, let's only consider the regime, say, $t \geq 1$. Second, I'm not worried about the constant in the big-O, but the constant of $1/2$ in the exponent should stay fixed -- note that $e^{-t^2/2}/t = e^{-t^2/2 - \ln(t)} \leq e^{-O(t^2)}$. So this is really a very fine distinction I am asking about (I'm tempted to say "it's entirely academic").

One stronger property that is not true is that a subgaussian variable's tail is dominated by $\Phi$. For example, a Rademacher variable $X$ (in $\{\pm 1\}$ with probability $0.5$ each) has $\Pr[X \geq 1] = 0.5$, which is larger than $\Pr[N \geq 1]$ for a standard normal $N$. But this seems like the "worst case", so it still seems hopeful to me that $(*)$ could hold for some constant.

(P.S. I was initially assuming that any conclusions here would translate smoothly to $\sigma$-subgaussian variables, where $\mathbb{E}[e^{tX}] \leq e^{\sigma^2 t^2/2}$. But maybe that's not true....)

$$\newcommand{\si}{\sigma}\newcommand{\R}{\mathbb{R}}\newcommand{\ch}{\operatorname{ch}}$$Let $$X$$ be a $$\sigma$$-sub-Gaussian random variable (r.v.) for some real $$\sigma>0$$, that is, $$\begin{equation*} M_X(t):=Ee^{tX}\le e^{\sigma^2t^2/2}\quad\text{for all real t}. \tag{1} \end{equation*}$$ Then the standard upper bound on $$P(X\ge u)$$ is $$e^{-u^2/(2\si^2)}$$, for each real $$u\ge0$$.

Note that (1) implies that the left and right derivatives of the moment generating function $$M_X$$ are $$0$$, and hence $$EX=0$$. So, the standard upper bound $$e^{-u^2/(2\si^2)}$$ on $$P(X\ge u)$$ can be indeed improved -- see Section 3.2.

However, any such improvement must be asymptotically negligible for large $$u$$. Specifically, for any upper bound $$B(u)$$ on $$P(X\ge u)$$ valid for all $$\si$$-sub-Gaussian random r.v.'s $$X$$ we have $$B(u)\ge e^{-u^2/(2\si^2)}(1-o(1))$$; here and in what follows, all asymptotic relations are given for $$u\to\infty$$.

Indeed, by simple rescaling, without loss of generality (wlog) $$\si=1$$. So, we have to show that $$\begin{equation*} P_u:=\sup_{X\in S}P(X\ge u)\ge e^{-u^2/2}(1-o(1)), \tag{2} \end{equation*}$$ where $$S$$ is the set of all $$1$$-sub-Gaussian random r.v.'s.

Here is a proof of (2). For $$p\in(0,1)$$ and real $$u>0$$, let $$X_{p,u}$$ be any r.v. such that $$\begin{equation*} P(X_{p,u}=u)=P(X_{p,u}=-u)=p/2,\quad P(X_{p,u}=0)=1-p. \tag{2.5} \end{equation*}$$ We will have $$X_{p,u}\in S$$ iff $$1-p+p\ch tu\le e^{t^2/2}$$ for all real $$t$$, that is, iff $$\begin{equation*} p\le p_u:=\inf_{t\in\R}r_u(t)=\inf_{t\ge0}r_u(t) \tag{3} \end{equation*}$$ where $$\ch:=\cosh$$ and $$\begin{equation*} r_u(t):=\frac{e^{t^2/2}-1}{\ch tu-1} \end{equation*}$$ for real $$t\ne0$$, with $$r_u(0):=r_u(0+)=r_u(0-)=1/u^2$$. Since $$r_u(\infty-)=\infty$$ and the function $$r_u$$ is even and continuous, the infimum in (3) is attained at some $$t_u\in[0,\infty)$$, so that $$\begin{equation*} p_u=r_u(t_u). \tag{4} \end{equation*}$$

Since the set $$[0,\infty]$$ is compact, wlog one of the following cases must occur:

Case 1: $$t_u=0$$. Then $$\begin{equation} p_u=r_u(0)=\frac1{u^2}>>e^{-u^2/2}. \tag{5} \end{equation}$$ Here and in the sequel, we write $$a>>b$$ for $$a/b\to\infty$$.

Case 2: $$t_u\downarrow0$$ and even $$t_u u\to0$$. Then $$\begin{equation} p_u=\frac{e^{t_u^2/2}-1}{\ch t_u u-1}\sim\frac1{u^2}>>e^{-u^2/2}. \tag{6} \end{equation}$$

Case 3: $$t_u\downarrow0$$ and $$t_u u\to c$$ for some $$c\in(0,\infty)$$. Then $$t_u\sim c/u$$ and hence $$\begin{equation} p_u=\frac{e^{t_u^2/2}-1}{\ch t_u u-1}\sim\frac{t_u^2/2}{\ch c-1} \sim\frac{c^2/2}{\ch c-1}\frac1{u^2}>>e^{-u^2/2}. \tag{7} \end{equation}$$

Case 4: $$t_u\downarrow0$$ and $$v:=t_u u\to\infty$$. Then $$v=o(u)$$ and hence $$\begin{equation} p_u=\frac{e^{t_u^2/2}-1}{\ch t_u u-1}\sim\frac{v^2/2}{e^v/2}\frac1{u^2} >>\frac{e^{-v}}{u^2}>>e^{-u^2/2}. \tag{8} \end{equation}$$

Case 5: $$t_u\to c$$ for some $$c\in(0,\infty)$$. Then $$\begin{equation} p_u=\frac{e^{t_u^2/2}-1}{\ch t_u u-1}\sim\frac{e^{c^2/2}-1}{e^{cu}/2}>>e^{-u^2/2}. \tag{9} \end{equation}$$

Case 6: $$t_u\to\infty$$. Then $$\begin{equation} p_u=\frac{e^{t_u^2/2}-1}{\ch t_u u-1}\sim\frac{e^{t_u^2/2}}{e^{t_u u}/2}\ge2e^{-u^2/2}. \tag{10} \end{equation}$$

Thus, in all cases $$\begin{equation} p_u\ge(2-o(1))e^{-u^2/2}. \tag{11} \end{equation}$$ Also, if we choose $$p=p_u$$, then clearly the non-strict inequality in (3) will hold. So, $$X_{p_u,u}\in S$$ and hence, by (2) and (2.5), $$\begin{equation*} P_u\ge P(X_{p_u,u}\ge u)=p_u/2. \end{equation*}$$ Now (2) follows by (11). $$\Box$$

• Thanks, I think this fully answers my question!
– usul
Apr 15 at 17:17

Theorem 3.1 of these lecture notes by Omar Rivasplata may be relevant:

Theorem. Let $$X$$ be a centered random variable. The following statements are equivalent:

(i) For some positive constant $$b$$, we have for each $$t\in\mathbf R$$, $$\mathbb E[e^{tX}]\leqslant e^{b^2t^2/2}$$;

(ii) for some positive constant $$c$$, we have for each positive $$\lambda$$, $$\mathbb P(|X|\geqslant \lambda)\leqslant 2e^{-c\lambda^2}$$.

Hence taking a (centered) random variable such that the tails behave like $$e^{-ct^2}$$ when $$t$$ is large, we cannot get the same bound as in the Gaussian case.

• Thanks! As with Mark's answer (but more subtle here) the issue of the constant in the exponent arises. I think the constant of $1/2$ in the exponent must stay fixed for the question to be interesting, since e.g. $e^{-t^2} \leq e^{-t^2/2}/t$ for most $t$. So concretely, the translation between $b$ and $c$ in the theorem probably won't be tight enough (true?) -- I think you'd want it to hold with $c = b^2/2$. On the other hand, this illustrates just how fine are the hairs I'm splitting in this question....
– usul
Jul 24 '15 at 1:42

It depends on exactly what you mean by "of the form ($*$)". As Davide points out (and as you certainly know if you've been reading Boucheron, Lugosi, and Massart), for centered subgaussian random variables you can get a tail bound of the form $e^{-ct^2}$. For small $t$ this is actually better than ($*$). On the other hand, for sufficiently large $t$, $$e^{-t^2/2} \ge \frac{e^{-t^2/2}}{t} = e^{-\frac{t^2}{2}-\log t} \ge e^{-t^2/4},$$ simply because $\log t \ll t^2$ when $t \to \infty$. (Actually $t$ doesn't even have to be that large.) So if you're really not worried about constants, this is the same thing.

• Thanks -- I was aware of this point, and meant to refer to the constant out front (in the big O of $(*)$), not in the exponent. Should have specified!
– usul
Jul 24 '15 at 1:20