Show that Markov's inequality is as tight as it possible. Given a positive integer $k$, describe a random variable $X$ that assumes only non-negative values:
$$\Pr[X \geq k E[X] ] = 1/k.$$
Using Markov's bound, we can show at most $1/k$. But how to show equality?! My question to be exact what is the idea to prove the tightness of this bound!
Best Answer
Consider a random variable $X$ which takes the value $1$ with probability $1/k$ and $0$ with probability $1-1/k$.