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$
  • $\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 '16 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 '16 at 0:22
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$
  • $\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 '16 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 '16 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 '16 at 15:35
0
$\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$

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.