Sum of stochastic varibles in [-1,1]

If $X = \sum_i^n X_i$ and all $X_i \in [-1,1]$ , then $\textnormal{\textbf{Pr}}\left[X \geq t \right] \leq e^{-t^2/(2n)}$
How do we prove this? We start off with Markov’s bound:

$\textnormal{\textbf{Pr}}\left[X \geq t \right] = \textnormal{\textbf{Pr}}\left[e^{\lambda X} \geq e^{\lambda t}\right] \leq \frac{\textnormal{\textbf{E}}\left[ e^{\lambda X}\right]}{e^{\lambda t}}$

Due to independence, we can say that

$\textnormal{\textbf{E}}\left[ e^{\lambda X}\right] = \textnormal{\textbf{E}}\left[ e^{\lambda \sum_i^n X_i} \right] = \textnormal{\textbf{E}}\left[ \prod_i^n e^{\lambda X_i}\right] = \prod_i^n \textnormal{\textbf{E}}\left[ e^{\lambda X_i}\right]$

If we can find a linear function $f(x) = ax + b$ that approximates (overestimates) $e^x$ in [−1,1], then we can use the linearity of the expected value to find a bound. The function that does the trick is

$f(x) = \frac{e^{\lambda}-e^{-\lambda}}{2}x +\frac{e^{\lambda}+e^{-\lambda}}{2}.$

Now, we can see that

$\prod_i^n \textnormal{\textbf{E}}\left[ e^{\lambda X_i}\right] \leq \prod_i^n \textnormal{\textbf{E}}\left[f(e^{\lambda X_i)}\right] = \prod_i^n \textnormal{\textbf{E}}f\left(\left[e^{\lambda X_i}\right]\right) =\prod_i^n f\left(0\right) = \left(\frac{e^{\lambda}+e^{-\lambda}}{2}\right)^n.$
$\frac{e^{\lambda}+e^{-\lambda}}{2} \leq e^{\lambda^2/2} \implies \prod_i^n \textnormal{\textbf{E}}\left[ e^{\lambda X_i}\right] \leq \left(e^{\lambda^2/2}\right)^n$

$\textnormal{\textbf{Pr}}\left[X \geq t \right] =\textnormal{\textbf{Pr}}\left[e^{\lambda X} \geq e^{\lambda t}\right] \leq \frac{\left(e^{\lambda^2/2}\right)^n}{e^{\lambda t}}.$

Minimum occurs at $\lambda = t/n$ , hence

$\textnormal{\textbf{Pr}}\left[X \geq t \right] \leq e^{-t^2/(2n)}$

grocid.net

scribbles from past, present and possibly future

Sum of stochastic varibles in [-1,1]

Leave a Reply Cancel reply

Menu

grocid.net

scribbles from past, present and possibly future

Share this:

Like this:

Leave a Reply Cancel reply

Menu