4
$\begingroup$

Markov's inequality states that $Pr(X \geq tE(X)) \leq 1/t$. This is great for asking "What is the probability that we get more than t times our expected value". However, if rather than more, we want to ask what is the probability that we get LESS than our expected value, how is this handled?

Say our expected value is $n/4$. If we wanted to ask what the probability is that we'd get less than $n/6$, intuitively I'd say

"It is 1 - the probability that we get greater than or equal to n/6"

, but that doesn't seem to be working out for me. How is this accomplished with Markov's inequality?

1 Answers 1

2

The probability you want cannot be bounded with the given data. On the one hand it could be $0$, if for example the random variable is zero, and on the other hand it could be close to $1$, if for example the random variable is $0$ w.p. $1-\epsilon$ and $n/4\epsilon$ w.p. $\epsilon$.

If you want an upper bound on such a probability then you need to know that your original random variable $X$ is bounded by some upper bound $B$. Then you consider the non-negative random variable $B-X$ and use the usual Markov's inequality.