If 
![X_i \in [-1,1]](https://s0.wp.com/latex.php?latex=X_i+%5Cin+%5B-1%2C1%5D&bg=ffffff&fg=000000&s=0 "X_i \in [-1,1]")
How do we prove this? We start off with Markov’s bound:
![\textnormal{\textbf{Pr}}\left[X \geq t \right] \leq e^{-t^2/(2n)}](https://s0.wp.com/latex.php?latex=%5Ctextnormal%7B%5Ctextbf%7BPr%7D%7D%5Cleft%5BX+%5Cgeq+t+%5Cright%5D+%5Cleq+e%5E%7B-t%5E2%2F%282n%29%7D&bg=ffffff&fg=000000&s=0 "\textnormal{\textbf{Pr}}\left[X \geq t \right] \leq e^{-t^2/(2n)}")
![\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}}](https://s0.wp.com/latex.php?latex=%5Ctextnormal%7B%5Ctextbf%7BPr%7D%7D%5Cleft%5BX+%5Cgeq+t+%5Cright%5D+%3D+%5Ctextnormal%7B%5Ctextbf%7BPr%7D%7D%5Cleft%5Be%5E%7B%5Clambda+X%7D+%5Cgeq+e%5E%7B%5Clambda+t%7D%5Cright%5D+%5Cleq+%5Cfrac%7B%5Ctextnormal%7B%5Ctextbf%7BE%7D%7D%5Cleft%5B+e%5E%7B%5Clambda+X%7D%5Cright%5D%7D%7Be%5E%7B%5Clambda+t%7D%7D&bg=ffffff&fg=000000&s=0 "\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]](https://s0.wp.com/latex.php?latex=%5Ctextnormal%7B%5Ctextbf%7BE%7D%7D%5Cleft%5B+e%5E%7B%5Clambda+X%7D%5Cright%5D+%3D+%5Ctextnormal%7B%5Ctextbf%7BE%7D%7D%5Cleft%5B+e%5E%7B%5Clambda+%5Csum_i%5En+X_i%7D+%5Cright%5D+%3D+%5Ctextnormal%7B%5Ctextbf%7BE%7D%7D%5Cleft%5B+%5Cprod_i%5En+e%5E%7B%5Clambda+X_i%7D%5Cright%5D+%3D+%5Cprod_i%5En+%5Ctextnormal%7B%5Ctextbf%7BE%7D%7D%5Cleft%5B+e%5E%7B%5Clambda+X_i%7D%5Cright%5D+&bg=ffffff&fg=000000&s=0 "\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 
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.](https://s0.wp.com/latex.php?latex=%5Cprod_i%5En+%5Ctextnormal%7B%5Ctextbf%7BE%7D%7D%5Cleft%5B+e%5E%7B%5Clambda+X_i%7D%5Cright%5D+%5Cleq+%5Cprod_i%5En+%5Ctextnormal%7B%5Ctextbf%7BE%7D%7D%5Cleft%5Bf%28e%5E%7B%5Clambda+X_i%29%7D%5Cright%5D+%3D+%5Cprod_i%5En+%5Ctextnormal%7B%5Ctextbf%7BE%7D%7Df%5Cleft%28%5Cleft%5Be%5E%7B%5Clambda+X_i%7D%5Cright%5D%5Cright%29+%3D%5Cprod_i%5En+f%5Cleft%280%5Cright%29+%3D+%5Cleft%28%5Cfrac%7Be%5E%7B%5Clambda%7D%2Be%5E%7B-%5Clambda%7D%7D%7B2%7D%5Cright%29%5En.&bg=ffffff&fg=000000&s=0 "\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](https://s0.wp.com/latex.php?latex=%5Cfrac%7Be%5E%7B%5Clambda%7D%2Be%5E%7B-%5Clambda%7D%7D%7B2%7D+%5Cleq+e%5E%7B%5Clambda%5E2%2F2%7D+%5Cimplies+%5Cprod_i%5En+%5Ctextnormal%7B%5Ctextbf%7BE%7D%7D%5Cleft%5B+e%5E%7B%5Clambda+X_i%7D%5Cright%5D+%5Cleq+%5Cleft%28e%5E%7B%5Clambda%5E2%2F2%7D%5Cright%29%5En&bg=ffffff&fg=000000&s=0 "\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}}.](https://s0.wp.com/latex.php?latex=%5Ctextnormal%7B%5Ctextbf%7BPr%7D%7D%5Cleft%5BX+%5Cgeq+t+%5Cright%5D+%3D%5Ctextnormal%7B%5Ctextbf%7BPr%7D%7D%5Cleft%5Be%5E%7B%5Clambda+X%7D+%5Cgeq+e%5E%7B%5Clambda+t%7D%5Cright%5D+%5Cleq+%5Cfrac%7B%5Cleft%28e%5E%7B%5Clambda%5E2%2F2%7D%5Cright%29%5En%7D%7Be%5E%7B%5Clambda+t%7D%7D.&bg=ffffff&fg=000000&s=0 "\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 
Advertisements
If
How do we prove this? We start off with Markov’s bound:
Due to independence, we can say that
If we can find a linear function
Now, we can see that
So
Minimum occurs at
