11
$\begingroup$

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.

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

1 Answer 1

4
$\begingroup$

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

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

Not the answer you're looking for? Browse other questions tagged .