Markov's Inequality Markov's Inequality: For nonnegative X,for any t >0, E[X] Pr[X≥t≤ t Proof: f(x) 1 ifX≥t, →Y≤ X ≤ X E(X] Pr[X≥t=E[Y]≤E p(Xza) tight if we only know the expectation of XMarkov’s Inequality Markov’s Inequality: Pr[X ⇥ t] E[X] t . For nonnegative X , for any t > 0, Y ⇥ X t ⇥ ⇥ X t , Pr[X t] = E[Y ] E X t ⇥ = E[X] t . Proof: Y = 1 if X t, 0 otherwise. Let tight if we only know the expectation of X