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?

  • $\begingroup$ what do you mean no relationship? they are real numbers, real numbers are totally ordered $\endgroup$
    – user515599
    Aug 10 '19 at 6:55
  • $\begingroup$ My guess is you're mixing up the logical scopes of the variables. Are you comfortable with logical statements involving $\forall$ and $\exists$? $\endgroup$ Aug 10 '19 at 7:13
  • $\begingroup$ I feel like you could use his argument to take two completely unrelated variables X and Y. Then saying I will prove X>Y by showing a counterexample for X$\leq$ Y. Showing that X$\leq$ Y is falase does not show X>Y right? $\endgroup$
    – Qwertford
    Aug 10 '19 at 7:51
  • $\begingroup$ I am comfortable with for all and existence statements.@BrianMoehring $\endgroup$
    – Qwertford
    Aug 10 '19 at 7:52

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.


Note: This ended up going a little deeper into the details than I initially intended. Perhaps if I ran this by a textbook editor, it could be made simpler, but I couldn't see anything I could cut out without making technical errors. If this feels like it answers your question and you don't understand any part, please ask for clarification in the comments and I'll try to respond.

Logically, Markov's inequality has the form

$$\forall P \in \mathcal{P}, \forall X \in \mathcal{X}, \forall \alpha \in \mathcal{A}, P(X \geq \alpha) \leq \frac{E[X]}{\alpha}$$

where $\mathcal{P}$ is the set of real probability measures, $\mathcal{A}$ is the set of positive real numbers, and $\mathcal{X}$ is the class of non-negative random variables.

In order to prove this by contradiction, we assume the negation, which has the equivalent logical forms

$$\lnot \left(\forall P \in \mathcal{P}, \forall X \in \mathcal{X}, \forall \alpha \in \mathcal{A}, P(X \geq \alpha) \leq \frac{E[X]}{\alpha} \right) \\ \exists P \in \mathcal{P}, \exists X \in \mathcal{X}, \exists\alpha \in \mathcal{A}, \lnot\left(P(X \geq \alpha) \leq \frac{E[X]}{\alpha} \right)$$

The important detail here is there are no free variables: all variables are bound by some scope. That is, within the scope, $P(X\geq \alpha)$ should not be treated as a function of unknown variables but rather as a real constant (since in any particular instantiation, it will be a real constant). Similarly, within the logical scope, $\frac{E[X]}{\alpha}$ should be treated as a real constant, and for real constants $r$ and $s,$ we know that the negation of $r\leq s$ is $r > s,$ so the negation of Markov's inequality has the final form

$$\exists P \in \mathcal{P}, \exists X \in \mathcal{X}, \exists\alpha \in \mathcal{A}, P(X \geq \alpha) > \frac{E[X]}{\alpha}$$

This is why, in a proof by contradiction of Markov's inequality, we assume $$\mbox{There is a probability }P, \mbox{ a non-negative random variable } X, \\ \mbox{ and a positive } \alpha, \mbox{ such that } P(X \geq \alpha) > \frac{E[X]}{\alpha} $$ (for a valid proof of the resulting contradiction, see saz's post)


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.