Markov's inequality says:
$P(X\geq \alpha ) \leq \frac{E[X] }{\alpha} $
I know the actual proof of this theorem, but i was talking to someone who used a proof by contradiction to prove this. Suppose $P(X\geq \alpha ) > \frac{E[X] }{\alpha} $ and assume that X can only take on values larger than alpha, then $\alpha>E[X]$ is the contradiction.
I think this is incorrect because it does not take into account the possibility that there is no relationship between the left and right hand side at all. Is this right? Under what circumstances can you use proof by contradiction?
Best Answer
I agree with you that the argument is not correct. We cannot assume that "$X$ takes only values larger than $\alpha$". For this we would need that $P(X \geq \alpha)=1$ but this does not follow from the inequality $P(X \geq \alpha)>E(X)/\alpha$ (... unless $\alpha \leq E(X)$, but in this case Markov's inequality is trivial anyway). The conclusion of the "proof" is also wrong ($\alpha>E(X)$ is no contradiction).
Here is a proof by contradiction: Suppose that $P(X \geq \alpha) > E(X)/\alpha$. Then
$$E(X) \geq E(X 1_{\{X \geq \alpha\}}) \geq \alpha P(X \geq \alpha) > E(X)$$
which is a contradiction.