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