I found this question while browsing through "The Probabilistic Method", by Noga Elon.

Let X and Y be 2 independent and identically distributed real valued random variables. Prove that: $$P(|X-Y| \leq 2) \leq 3P(|X-Y| \leq 1)$$

So I tried the following:

$$P\{|X-Y| \leq 2\} = P\{|X-Y| \leq 1\} + P\{X-Y \in (1,2]\cup[-2,-1)\}$$ $$= P\{|X-Y| \leq 1\} + P\{X-Y \in (1,2]\} + P\{X-Y \in [-2,-1)\}$$ $$= P\{|X-Y| \leq 1\} + 2P\{X-Y \in (1,2]\}$$ where the last step follows because $X-Y$ has a symmetric distribution. NB: A random variable Z has symmetric distribution if $$P(Z \leq z) = P(Z \geq -z) \quad \forall z \in \mathbb{R}$$

Thus the problem boils down to showing $$P\{X-Y \in (1,2]\} \leq P(|X-Y| \leq 1)$$ and I would be done. Unfortunately, I don't know how to proceed from here. I appreciate any help, hints, useful comments etc. I receive.

  • $\begingroup$ What does iid mean? $\endgroup$ – Dominik Nov 25 '12 at 16:45
  • 1
    $\begingroup$ independent and identically distributed. I'll edit it. $\endgroup$ – Gautam Shenoy Nov 25 '12 at 16:46

A proof is given in "The 123 Theorem and its extensions" by Noga Alon, Raphael Yuster. (See also this question.)

  • 1
    $\begingroup$ The '123 theorem' looks so simple. The solution seems really wicked! I have been trying this problem for four days now :( $\endgroup$ – Isomorphism Nov 26 '12 at 7:29

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.