If and all
, then
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 that approximates (overestimates)
in [−1,1], then we can use the linearity of the expected value to find a bound. The function that does the trick is
Now, we can see that
So
Minimum occurs at , hence