10
$\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.

  • 1
    independent and identically distributed. I'll edit it.2012-11-25

1 Answers 1

3

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

  • 1
    The '123 theorem' looks so simple. The solutio$n$ seems really wicked! I have bee$n$ trying this proble$m$ for four days now :(2012-11-26