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

Advertisements