Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
What does iid mean? –  Dominik Nov 25 '12 at 16:45
independent and identically distributed. I'll edit it. –  Gautam Shenoy Nov 25 '12 at 16:46
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
The '123 theorem' looks so simple. The solution seems really wicked! I have been trying this problem for four days now :( –  Isomorphism Nov 26 '12 at 7:29
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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