Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge 8: Sub-Gaussian Variables

  1. Nov 25, 2013 #1

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    A random variable X is called sub-gaussian if
    [tex] P( |X| > t) \leq 2e^{-K t^2} [/tex]
    for some constant K. Equivalently, the probability density p(x) is sub-gaussian if
    [tex] \int_{-t}^{t} p(x) dx \geq 1 - 2 e^{-Kt^2}. [/tex]

    The challenge: Prove that the standard normal distribution (with mean 0 and variance 1) is sub-gaussian.
     
  2. jcsd
  3. Nov 25, 2013 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I haven't found a solution yet, but here's a method that might be useful.

    The standard normal distribution has the following probability density function:
    $$p(x) = \frac{1}{\sqrt{2\pi}} e^{-x^2/2}$$
    Therefore we wish to prove that there exists some ##K## such that
    $$\int_{-\infty}^{\infty} r_t(x) p(x) dx \geq 1 - 2e^{-Kt^2}$$
    where
    $$r_t(x) = \begin{cases}
    1 & \text{ if }|x| < t \\
    0 & \text{ if }|x| > t\\
    \end{cases}$$
    Note that in general, the integral of a function is equal to its Fourier transform evaluated at zero:
    $$\int_{-\infty}^{\infty}f(x) dx = \left. \int_{-\infty}^{\infty} f(x) e^{-2\pi i u x} dx \right|_{u = 0} = \hat{f}(0)$$
    where ##\hat{f}## is the Fourier transform of ##f##:
    $$\hat{f}(u) = \int_{-\infty}^{\infty}f(x) e^{-2\pi i u x} dx$$
    We may therefore express our desired integral (let's call it ##I##) in terms of Fourier transforms:
    $$I = \int_{-\infty}^{\infty} r_t(x) p(x) dx = \widehat{r_t p}(0)$$
    where ##\widehat{r_t p}## is the Fourier transform of the product ##r_t p##. It's easy to show that the Fourier transform of a product is equal to the convolution of the Fourier transforms of the factors:
    $$\widehat{r_t p}(u) = \int_{-\infty}^{\infty} \widehat{r_t}(u-v)\widehat{p}(v) dv$$
    Evaluating at ##u = 0##, we get
    $$I = \widehat{r_t p}(0) = \int_{-\infty}^{\infty} \widehat{r_t}(-v) \widehat{p}(v) dv$$
    Let us now compute ##\widehat{r_t}## and ##\widehat{p}##. Starting with the definition of the Fourier transform, we obtain
    $$\begin{align}
    \widehat{r_t}(v) &= \int_{-\infty}^{\infty} r_t(x) e^{-2\pi i v x} dx \\
    &= \int_{-t}^{t} e^{-2\pi i v x} dx \\
    &= \int_{-t}^{t} \cos(2\pi v x) dx \\
    &= 2 \int_{0}^{t} \cos(2\pi v x) dx \\
    &= \left. 2 \frac{\sin(2\pi v x)}{2\pi v} \right|_{x = 0}^{x = t} \\
    &= 2 \frac{\sin(2 \pi v t)}{2\pi v} \\
    &= \frac{\sin(2\pi v t)}{\pi v}\\
    \end{align}$$
    Note that the result is an even function of ##v##, i.e., ##\widehat{r_t}(-v) = \widehat{r_t}(v)##, so we can simplify our expression for ##I## to
    $$I = \int_{-\infty}^{\infty} \widehat{r_t}(v) \widehat{p}(v) dv$$
    Next we calculate ##\hat{p}##, again starting from the definition. We have
    $$\begin{align}
    \hat{p}(v) &= \int_{-\infty}^{\infty} p(x) e^{-2 \pi i v x} dx \\
    &= \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} e^{-x^2/2}e^{-2\pi i v x} dx\\
    &= \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} \exp\left(-\frac{1}{2} (x^2 + 4\pi i v x)\right)dx \\
    &= \exp\left(-\frac{1}{2} 4 \pi^2 v^2\right) \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} \exp\left(-\frac{1}{2} (x + 2\pi i v)^2\right) dx \\
    &= \exp\left(-\frac{1}{2} 4 \pi^2 v^2\right) \frac{1}{\sqrt{2\pi}} \cdot \sqrt{2\pi} \\
    &= \exp(-2\pi^2 v^2)
    \end{align}$$
    Plugging the expressions for ##\widehat{r_t}## and ##\hat{p}## into our integral, we obtain
    $$I = \int_{-\infty}^{\infty}\widehat{r_t}(v) \widehat{p}(v) dv =
    \int_{-\infty}^{\infty} \frac{\sin(2\pi v t)}{\pi v} \exp(-2\pi^2 v^2) dv$$
    Now if I can find the right lower bound for the integrand as a function of ##v## and ##t##, the result might follow. Or I could be barking up the wrong tree.

    Intuitively, as ##t## increases, ##\sin(2\pi v t)/(\pi v)## becomes a taller and skinnier function centered at ##v = 0##, although with tails that decay on the order of ##1/v##, so the oscillations are important! Most of the value of ##I## is hopefully determined by the part spanned by the "main peak" of ##\sin(2\pi v t)/(\pi v)##, which is the part for which ##|v| < 1/(2t)##.

    I think it's true that
    $$I > \int_{-1/t}^{1/t} \frac{\sin(2\pi v t)}{\pi v} \exp(-2\pi^2 v^2) dv$$
    because outside the interval ##[-1/t, 1/t]## you could approximate the integrand as an alternating series whose first term is positive.
     
    Last edited: Nov 25, 2013
  4. Nov 30, 2013 #3
    Let's try this.

    We wish to prove that ##\displaystyle 1\leq\frac{\sqrt{2}}{\sqrt{\pi}}\int\limits_{[0,t]}e^{-\frac{x^2}{2}}\mathrm{d}x+2e^{-kt^2}=f(t)##.

    Attempt 1:
    Expanding by power series, we get $$\frac{\sqrt{2}}{\sqrt{\pi}}\int\limits_{[0,t]}e^{-\frac{x^2}{2}}\mathrm{d}x=\frac{\sqrt{2}}{\sqrt{\pi}}\sum_{0\leq n}\frac{(-1)^n t^{2n+1}}{2^n(2n+1)n!}.$$

    For ##2e^{-kt^2}##, we expand and get ##\displaystyle 2e^{-kt^2}=2\sum_{m\geq 0}\frac{(-1)^mk^mt^{2m}}{m!}##.

    Let ##k=\frac{1}{2}## for ease of notation. After a myriad of simplifications and a couple series manipulations which I am not going to LaTeX out, we just need to prove $$1\leq 2\sum_{n\geq 0}(-1)^n\frac{t^{2n}(t+\sqrt{2\pi}(2n+1))}{\sqrt{2\pi}2^n(2n+1)n!}.$$

    By properties of alternating series, I'm pretty sure that one can show the RHS is always greater than 1.

    Attempt 2:
    Note that $$\frac{d}{dt}\left(\frac{\sqrt{2}}{\sqrt{\pi}}\int\limits_{[0,t]}e^{-\frac{x^2}{2}}\mathrm{d}x+2e^{-kt^2}\right)=\sqrt{\frac{2}{\pi}}e^{-\frac{1}{2}t^2}-4kte^{-kt^2}=e^{-\frac{1}{2}t^2}(\sqrt{\frac{2}{\pi}}-2t).$$ Letting ##k=1/2## again, for convenience. Then, we note that ##max(f)=f\left(\sqrt{\frac{1}{2\pi}}\right)>1##. Since ##f## is [strike]increasing[/strike] (clearly decreasing with an asymptote at 1) for all ##t>\sqrt{\frac{1}{2\pi}}## and ##f(t)>1## for all ##0\leq t\leq \sqrt{\frac{1}{2\pi}}##, the result follows.

    Not sure if either of these is right. They were pretty ugly.

    Edit: Ignore the second part. I clearly did something horribly wrong with the derivatives. >_>
     
    Last edited: Nov 30, 2013
  5. Dec 1, 2013 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I guess we just consider t≥0?
    For t=0, it is trivial (left side 1/2, right side 1), consider t>0 now.

    We want to show
    $$\int_{-t}^{t} p(x) dx \geq 1 - 2 e^{-Kt^2}$$
    As the normal distribution is symmetric, this can be written as
    $$1-2\int_{t}^{\infty} p(x) dx \geq 1 - 2 e^{-Kt^2}$$
    or
    $$\int_{t}^{\infty} p(x) dx \leq e^{-Kt^2}$$

    As a plot and with the example K=1/2, this means the red line has to be above the blue line in the WolframAlpha plot
    (if the url does not work, the query: "plot int(1/sqrt(2pi)*exp(-y^2/2), y from x to infinity), e^(-x^2/2)")

    Let's find an upper bound for the integral. As the integrand is monotonically decreasing,
    $$\int_{t}^{\infty} p(x) dx \\
    \leq \sum_{i=0}^\infty p(t+i) \\
    = \frac{1}{\sqrt{2\pi}} \sum_{i=0}^\infty \exp\left(\frac{-(t+i)^2}{2}\right) \\
    < \frac{1}{\sqrt{2\pi}} \sum_{i=0}^\infty \exp\left(\frac{-t^2-2ti}{2}\right) \\
    = \frac{1}{\sqrt{2\pi}} \exp(-t^2/2) \sum_{i=0}^\infty \left(e^{-t}\right)^i
    $$
    As t>0, exp(-t)<1 so we can evaluate the sum.
    $$ = \frac{1}{\sqrt{2\pi}} \exp(-t^2/2) \frac{1}{1-e^{-t}}$$

    Let's fix ##K=\frac{1}{2}##. We have to show that
    $$\frac{1}{\sqrt{2\pi}} \exp(-t^2/2) \frac{1}{1-e^{-t}} \leq e^{-t^2/2}$$
    This is satisfied if
    $$\sqrt{2 \pi} (1-e^{-t}) \geq 1$$
    where equality gives approximately t ≈ 0.51. Therefore, the inequality is satisfied for t≥1.

    It is left to show the inequality for 0<t<1. In this interval, the LHS is ≤ 0.5, but ##e^{-t^2/2} > e^{-1/2} \approx 0.607 > 0.5.

    As a result, with K=1/2 the inequality is satisfied everywhere and the standard normal distribution is sub-gaussian.
     
  6. Dec 2, 2013 #5

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That seems like it would be hard - if t is sufficiently large the first bunch of terms will be increasing in magnitude (as they will have higher powers of t).

    mfb, that's a really nice solution, I like the idea of bounding the integral with a Riemann sum. k=1/2 is actually the best bound that I know of, but your proof is the first one that makes me think that it is genuinely tight as opposed to just convenient (since the sum should be a really good estimate if t is large).

    Any alternate proofs out there people can come up with?
     
  7. Dec 2, 2013 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Proof:

    $$\int_{t}^{\infty} p(x) dx \\
    {\bf \geq} \sum_{i=1}^\infty p(t+i) \\
    = \frac{1}{\sqrt{2\pi}} \sum_{i=1}^\infty \exp\left(\frac{-(t+i)^2}{2}\right) \\
    > \frac{1}{\sqrt{2\pi}} \exp(-\frac{(t+1)^2}{2})$$
    Where the last expression is simply the first term of the sum.

    Let's look at the inequality:
    $$\frac{1}{\sqrt{2\pi}} \exp(-\frac{(t+1)^2}{2}) < e^{-K t^2}$$
    This can be solved for K:
    $$c+(t+1)^2 > 2Kt^2$$
    Where ##c=\log(2 \pi)## is constant.
    $$K< \frac{c+(t+1)^2}{2t^2} = \frac{1}{2} + \frac{1}{t} + \frac{1+c}{2t^2}$$
    K cannot be larger than 1/2, or the inequality gets violated at some point.
     
    Last edited: Dec 2, 2013
  8. Dec 2, 2013 #7
    That's...awesome. In the series method I used, ##k=\frac{1}{2}## was actually what I considered an aesthetic choice. I chose it because it made the computations simple and lots of things cancelled to give something I knew would converge. That's pretty fantastic, when you think about how all of it connects. :approve:
     
  9. Dec 2, 2013 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    One part gives a nice sum, the other part gives the error function:

    $$ \sum_{n\geq 0}(-1)^n\frac{t^{2n}(t+\sqrt{2\pi}(2n+1))}{\sqrt{2\pi}2^n(2n+1)n!} \\
    = \sum_{n\geq 0}(-1)^n\frac{t^{2n}(\sqrt{2\pi}(2n+1))}{\sqrt{2\pi}2^n(2n+1)n!} + \sum_{n\geq 0}(-1)^n\frac{t^{2n}t}{\sqrt{2\pi}2^n(2n+1)n!} \\
    = \sum_{n\geq 0}(-1)^n\frac{t^{2n}}{2^nn!} + \frac{1}{\sqrt{2\pi}}\sum_{n\geq 0}(-1)^n\frac{t^{2n+1}}{2^n(2n+1)n!} \\
    = \sum_{n\geq 0}\frac{(-t^2/2)^n}{n!} + \frac{1}{\sqrt{2\pi}}\sum_{n\geq 0}(-1)^n\frac{t^{2n+1}}{2^n(2n+1)n!} \\
    = \exp\left(-\frac{t^2}{2}\right) + \frac{1}{\sqrt{2\pi}}\sum_{n\geq 0}(-1)^n\frac{t^{2n+1}}{2^n(2n+1)n!}$$
    Let's focus on the second part:
    $$\frac{1}{\sqrt{2\pi}}\sum_{n\geq 0}(-1)^n\frac{t^{2n+1}}{2^n(2n+1)n!} \\
    = \int dt \frac{d}{dt} \frac{1}{\sqrt{2\pi}}\sum_{n\geq 0}(-1)^n\frac{t^{2n+1}}{2^n(2n+1)n!} \\
    = \frac{1}{\sqrt{2\pi}} \int dt \sum_{n\geq 0}(-1)^n\frac{t^{2n}}{2^n n!} \\
    = \frac{1}{\sqrt{2\pi}} \int dt \exp\left(\frac{-t^2}{2}\right)$$
    Now we have to get the integration constant right: For t=0, the expression is 0.
    $$ = \frac{1}{\sqrt{2\pi}} \int_0^t dt' \exp\left(\frac{-t'^2}{2}\right)$$
    So now we are comparing a gaussian with the error function again. I think this went in a circle...

    We have to prove that$$1 \leq 2 \exp\left(-\frac{t^2}{2}\right) + \frac{2}{\sqrt{2\pi}} \int_0^t dt' \exp\left(\frac{-t'^2}{2}\right)$$
    Which is equivalent to (using the symmetry of the integral)
    $$1 - 2 \exp\left(-\frac{t^2}{2}\right) \leq \frac{1}{\sqrt{2\pi}} \int_{-t}^t dt' \exp\left(\frac{-t'^2}{2}\right)$$
    And that is exactly the initial problem statement. Okay, bad direction. Well now we have that in TeX.
     
    Last edited: Dec 2, 2013
  10. Dec 2, 2013 #9

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    mfb, you literally just reversed the steps that he took to arrive at that :p
     
  11. Dec 2, 2013 #10
    I'm literally crying with laughter right now. That was hilarious. :rofl::rofl::rofl:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge 8: Sub-Gaussian Variables
  1. Challenging problems (Replies: 6)

  2. Decimal 8? (Replies: 4)

  3. Master's Challenge (Replies: 15)

  4. A Euclidean Challenge (Replies: 10)

Loading...