Discussion 12B

Markov Bound

If

X

is nonnegative then

\Pr(X \geq a) \leq \frac{E[X]}{a}

.

Proof 1

E[X] = \sum_x x \Pr(X=x) \geq \sum_{x \geq a} x \Pr(X=x)

\geq \sum_{x\geq a} a \Pr(X=x) = a \Pr(X \geq a)

Proof 2

Let

I

be an indicator for the event

X \geq a

. Then

a I \leq X

because

if $X \geq a$ , then $a \cdot 1 \leq X$

if $X < a$ , then $a \cdot 0 \leq X$

Taking the expectations of both sides gives us

a E[I] \leq E[X]

, or

a \Pr(X \geq a) \leq E[X]

.

Chebyshev’s Inequality

For any random variable

X

, let

Y = (X - E[X])^2

. Since

Y

is nonnegative we can apply the Markov Bound to

Y

, so

\Pr(Y \geq a) \leq \frac{E[Y]}{a}

, or similarly

\Pr(Y \geq a^2) \leq \frac{E[Y]}{a^2}

.

The LHS

\Pr(Y \geq a^2) = \Pr( (X-E[X])^2 \geq a^2) = \Pr( | X - E[X] | \geq a)

.

The RHS

\frac{E[Y]}{a^2} = \frac{\mathrm{Var}(X)}{a^2}

.

Together, we get

\Pr( | X - E[X] | \geq a) \leq \frac{\mathrm{Var}(X)}{a^2}

.

With a substitution we get an alternate form

\Pr( | X - E[X] | \geq k \sigma) \leq \frac{1}{k^2}

.

Estimators

If there is some population parameter

p

, an unbiased estimator

\hat{p}

is a measurement for which

E[\hat p] = p

.

Iterated Expectation

E[X \mid Y]

is a conditional expectation.

E[X \mid Y] = \sum_x x \Pr(X=x \mid Y)

It is a function of

Y

: for any particular value of

Y=y

, what do we expect

X

to be? So

E[X \mid Y] = g(Y)

.

The expectation of this function

E_Y[g(Y)] = E_Y[ E[ X \mid Y ] ] = E[X]

.

This is also known as the law of total expectation because

E_Y [g(Y)] = \sum_y g(y) \Pr(Y=y) = \sum_y E[X \mid Y=y] \Pr(Y=y)

.

Taking it a couple steps further,

\sum_y E[X \mid Y=y] \Pr(Y=y)

= \sum_y \Big(\sum_x x \Pr(X=x \mid Y=y) \Big) \Pr(Y=y)

= \sum_{x,y} x \Pr(X=x \mid Y=y) \Pr(Y=y)

= \sum_{x,y} x \Pr(X=x, Y=y)

= \sum_{x} x \sum_y \Pr(X=x, Y=y)

= \sum_x x \Pr(X=x)

=E[X]

​​Markov Bound

​​Proof 1

​​Proof 2

​​Chebyshev’s Inequality

​​Estimators