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$

3 Answers 3

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
    Commented Apr 15, 2021 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
    Commented Jul 24, 2015 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
    Commented Jul 24, 2015 at 1:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .