6
$\begingroup$

Consider a random variable $X \ge 0$ which takes values in an interval $[0, b]$, and further $$ \text{P}(X \ge t) \le C \exp\left(\frac{-t^{2}}{B}\right), \quad \forall t \ge 0, $$ for given constants $C \gg 1$ and $B >0$.

Since $X$ is bounded, it is a sub-Gaussian variable, and its variance proxy can be upper bounded by $O\left((b-0)^{2}\right)$ based on the length of the interval.

Q1: First, a clarification on the definition: if we temporarily ignore the fact that $X$ is bounded (but taking into account that $X \ge 0$), then is the above tail bound enough to say that $X$ is sub-Gaussian? (E.g., does the value of $C$ matter?)

Q2: Using the tail bound, is it possible to get a better upper bound on the variance proxy? In particular, I saw a claim that based on the above tail bound, the moments of $X-\mathbb{E}[X]$ can upper be bounded by those of a Gaussian with variance $O(B \sqrt{\log{C}})$. Is that true?

Edit: To bound all moments of $X-\mathbb{E}[X]$ by those of a Gaussian with variance $\gamma$, I would need to show that $X-\mathbb{E}[X]$ is sub-Gaussian with variance proxy $\gamma > 0 $, i.e., that $\mathbb{E}[e^{s(X-\mathbb{E}[X])}] \le e^{s^{2}\gamma/2}$. Motivated by Michael's answer, which gives an upper bound on the variance $\sigma^{2}$ of $X$, we could put the question this way: is there a straightforward connection between $\gamma$ and $\sigma^{2}$? I see a related question here: Bound variance proxy of a subGaussian random variable by its variance

$\endgroup$
2
  • $\begingroup$ On your first question: Since $X \geq 0$ we have $P[X\geq t]=P[|X|\geq t]$ and so, even without the deterministic upper bound $b$, your inequality on $P[X\leq t]$ is the same as the definition of "sub-Gaussian" given here: en.wikipedia.org/wiki/Sub-Gaussian_random_variable $\endgroup$
    – Michael
    Sep 30, 2016 at 19:38
  • $\begingroup$ Thanks @Michael. I did see the wiki definition, but wanted to be sure since it did not agree with other definitions from more trusted sources. $\endgroup$
    – megas
    Oct 2, 2016 at 0:22

2 Answers 2

1
$\begingroup$

Considering both bounds, we know that: $$P[X > t] \leq \left\{ \begin{array}{ll} \min[1,C e^{-t^2/B}] &\mbox{ if $t \in [0,b)$} \\ 0 & \mbox{ if $t\geq b$} \end{array} \right. $$ This is the tightest bound since we can consider a random variable $W$ with $P[W>t]$ given exactly by the right-hand-side of the above inequality. Notice that $C e^{-t^2/B} \geq 1$ whenever $t \in [0, \sqrt{B\log(C)}]$. For simplicity assume that $b \geq \sqrt{B\log(C)}$.

We know that, for general nonnegative random variables $Y$, we have $Y=\int_{0}^{\infty} 1\{Y>t\}dt$ and hence $E[Y]=\int_{0}^{\infty}P[Y>t]dt$. Thus,

\begin{align} E[X^2] &= \int_{0}^{\infty} P[X^2>t]dt \quad \mbox{[since $X^2 \geq0$]}\\ &= \int_0^{\infty} P[X > \sqrt{t}]dt \quad \mbox{[since $X \geq 0$]}\\ &=\int_0^{B\log(C)} \underbrace{P[X>\sqrt{t}]}_{\leq 1}dt + \int_{B\log(C)}^{b^2}\underbrace{P[X>\sqrt{t}]}_{\leq Ce^{-t/B}}dt \quad \mbox{[since $P[X>b]=0$]} \\ &\leq B\log(C) + -CBe^{-t/B}|_{B\log(C)}^{b^2}\\ &=B\log(C) + B - CBe^{-b^2/B} \end{align} This is the best upper bound on $E[X^2]$ since it holds with equality for the random variable $W$ defined above. A simpler bound is then $E[X^2] \leq B\log(C) + B$, and this holds regardless of the value of $b$. (It even holds when $0\leq b < \sqrt{B\log(C)}$, since reducing the value of $b$ cannot increase the bound.)

In particular, $\sigma=\sqrt{Var(X)} \leq \sqrt{E[X^2]} \leq \sqrt{B + B\log(C)}$.

$\endgroup$
3
  • $\begingroup$ It can be shown that, for the case $b \geq \sqrt{B \log(C)}$ considered above, we have $B \log(C) + B - CB e^{-b^2/B} \leq b^2$ always, which is consistent with the fact that $B \log(C) + B - CB e^{-b^2/B}$ is the tightest upper bound on $E[X^2]$ and hence tighter than the upper bound $b^2$. $\endgroup$
    – Michael
    Sep 30, 2016 at 22:15
  • $\begingroup$ If $B \geq 2$ and $C \geq e$, then $\sqrt{B + B\log(C)} \leq B\sqrt{\log(C)}$. $\endgroup$
    – Michael
    Oct 2, 2016 at 13:20
  • $\begingroup$ The $O(B \sqrt{\log{C}})$ bound I mentioned was on $\sigma^{2}$, not $\sigma$. Of course the two bounds differ only by a factor of $\sqrt{\log{C}}$. $\endgroup$
    – megas
    Oct 2, 2016 at 15:35
1
$\begingroup$

(I figured that the statement of my second question is true. I am sharing a proof sketch for future reference.)


Let $\mu = \mathbb{E}\left[{X}\right]$, and define $Y = X- \mu$. It suffices to show that $$ \mathbb{E} \left[ \exp\left(\lambda \cdot Y\right) \right] \le \exp\left(\frac{1}{2} \cdot \sigma^{2} \cdot \lambda^{2}\right), \quad \lambda \in \mathbb{R}, $$ for $\sigma^{2} = O(B\sqrt{\log{C}})$. (In the sequel, I assume that $\log{C} \ge 1$.)

First, we derive an upper bound on the absolute moments of $Y$: \begin{align} \mathbb{E} \left[ \left\lvert{Y}\right\rvert^{p} \right] = \mathbb{E} \left[ |{X} - \mu |^{p} \right] \le \mathbb{E}\left[ \max\left\lbrace {X}, \mu\right\rbrace^{p} \right] \le \mathbb{E}\left[ {X}^{p} \right] + \mu^{p}, \end{align} where we have taken into account that $X\ge 0$ and in turn $\mu \ge 0$. Now, $X^{p}$ is a nonnegative random variable, and in turn \begin{align} \mathbb{E}\left[ X^{p} \right] &= \int_{0}^{\infty} \mathrm{P}\left( {X}^{p} \ge u\right) du = \int_{0}^{\infty} \mathrm{P}\left( {X}^{p} \ge t^{p}\right) \cdot {p} \cdot t^{p-1} dt \nonumber\\ &= \int_{0}^{\infty} \mathrm{P}\left( {X} \ge t\right) \cdot {p} \cdot {t^{p-1}} dt \nonumber\\ &= \underbrace{ \int_{0}^{t_{0}} \mathrm{P}\left( {X} \ge t\right) \cdot {p} \cdot {t^{p-1}} dt }_{I_{1}} + \underbrace{ \int_{t_{0}}^{\infty} \mathrm{P}\left( {X} \ge t\right) \cdot {p} \cdot {t^{p-1}} dt, }_{I_{2}} \label{sug-gaussian:X-pth-moment-start-ub} \end{align} for any $t_{0} \ge 0$. For $t_{0} = ({B}\sqrt{\log{C}})^{1/2}$, we have \begin{align} I_{1} = \int_{0}^{t_{0}} \mathrm{P}\left( {X} \ge t\right) \cdot {p} \cdot {t^{p-1}} dt \le \int_{0}^{t_{0}} {p} \cdot {t^{p-1}} dt = t_{0}^{p} = \left({B}\sqrt{\log{C}}\right)^{p/2}. \label{sug-gaussian:I1-ub} \end{align} For the second part, let $f(t) = {C} \cdot e^{-t^{2}/B}$ and $g(t) = e^{-t^{2}/\left({B}\sqrt{\log{C}}\right)}$. One can verify that $f(t) \le g(t)$ for $t \ge ({B}\sqrt{\log{C}})^{1/2}$ (assuming that $\log{C} \ge 1$). Then, \begin{align} I_{2} &= \int_{t_{0}}^{\infty} \mathrm{P}\left( {X} \ge t\right) \cdot {p} \cdot {t^{p-1}} dt \le \int_{t_{0}}^{\infty} f(t) \cdot {p} \cdot {t^{p-1}} dt %\nonumber\\& \le \int_{t_{0}}^{\infty} g(t) \cdot {p} \cdot {t^{p-1}} dt, \label{sug-gaussian:I2-ub} \end{align} It follows that for the particular choice of $t_{0}$, \begin{align} I_{2} &\le \int_{t_{0}}^{\infty} g(t) \cdot {p} \cdot {t^{p-1}} dt \le \int_{0}^{\infty} g(t) \cdot {p} \cdot {t^{p-1}} dt \nonumber\\ &\le \int_{0}^{\infty} e^{-t^{2}/(B\sqrt{\log{C}})} \cdot {p} \cdot {t^{p-1}} dt = (B \sqrt{\log{C}})^{p/2} \cdot \frac{p}{2} \cdot \Gamma\left( \frac{p}{2}\right) \end{align} Combining the bounds on the two parts, we have \begin{align} \mathbb{E}\left[ X^{p} \right] \le \left({B}\sqrt{\log{C}}\right)^{p/2} \cdot \left( 1 + \frac{p}{2} \cdot \Gamma\left( \frac{p}{2}\right) \right). \end{align} Specifically for $p=1$, we find \begin{align} \mu = \mathbb{E}\left[ X\right] \le 2 \cdot \left({B}\sqrt{\log{C}}\right)^{1/2}. \label{sub-gaussian:ub-on-mean} \end{align} Further, for any $p \ge 2$, \begin{align} \mathbb{E}\left[ X^{p} \right] \le \left({B}\sqrt{\log{C}}\right)^{p/2} \cdot 2^{p} \cdot \left( \frac{p}{2}\right)^{p/2}. \end{align} Finally, combining the above we find that for any $p \ge 2$, $$ \mathbb{E} \left[ \left\lvert{Y}\right\rvert^{p} \right] \le c^{\prime} \left({B}\sqrt{\log{C}}\right)^{p/2} \cdot 2^{p} \cdot \left( \frac{p}{2}\right)^{p/2}, $$ for some positive constant $c^{\prime}$.

Having the above upper bound on $\mathbb{E}\left[ |Y|^{p}\right]$, we can now show (see Lemma 5.5 in https://arxiv.org/pdf/1011.3027v7.pdf that \begin{align} \mathbb{E} \left[ \exp\left({\lambda}{Y}\right) \right] &= \exp(O\left((B\sqrt{\log{C}})^{2}\lambda^{2}\right)) \end{align} which is the desired result.

$\endgroup$

You must log in to answer this question.

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