4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

$\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$

$\endgroup$
1
  • $\begingroup$ Thanks, I think this fully answers my question! $\endgroup$ – usul Apr 15 at 17:17
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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.... $\endgroup$ – usul Jul 24 '15 at 1:42
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ – usul Jul 24 '15 at 1:20

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.