in Math 326 Words

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

So

\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)}

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Google photo

You are commenting using your Google account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s