1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

Consider a random variable $X$ which takes the value $1$ with probability $1/k$ and $0$ with probability $1-1/k$.

$\endgroup$
  • $\begingroup$ Thank you for your answer. It really helps me. I understand that "you give example" to show that it is tight so there is "no proof" as I understand. Also, I understand that when expected value is 1, then we have a tight bound for Markov's bound. So, thank you, I was thinking that there might be a proof. $\endgroup$ – YOUSEFY Sep 19 '17 at 6:21
  • $\begingroup$ To @Davide : Maybe you meant "$X$ which takes the value $1$ with probability $1/k$"? $\endgroup$ – Arundo Donax Sep 28 '17 at 17:00
  • $\begingroup$ @ArundoDonax You are right. $\endgroup$ – Davide Giraudo Sep 28 '17 at 19:00
  • $\begingroup$ @DavideGiraudo I believe X should take the value "k" not "1", with probability 1/k. $\endgroup$ – Toastgeraet Feb 17 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.