Exercise 1.6.3 from Alon & Spencer's *The Probabilistic Method*: prove that $Pr[|X-Y| \leq 2] \leq 3 Pr[|X-Y| \leq 1]$ for i.i.d. real RVs $X$ and $Y$

Doing a little reading over the break (The Probabilistic Method by Alon and Spencer); can't come up with the solution for this seemingly simple (and perhaps even a little surprising?) result:

(A-S 1.6.3) Prove that for every two independent identically distributed real random variables $X$ and $Y$, $$Pr[|X-Y| \leq 2] \leq 3 Pr[|X-Y| \leq 1].$$

Solution 1:

You may read the paper "The 123 theorem and its extensions" by Noga Alon and Raphael Yuster.

Solution 2:

I can prove it for the case when $Z = |X-Y|$ takes only integer values.

Let $q_i = P(Z=i)$ for $i=0,1,\dots$. Then, we need to show that $\frac{q_0+q_1}{q_0+q_1+q_2} \geq \frac{1}{3}$. This follows from the observation that $2q_0 \geq q_i$ for all $i$. This follows from Cauchy Schwarz inequality. Then,

$\begin{aligned} 3(q_0+q_1) &\geq (q_0+q_1+q_2) \\ 2(q_0+q_1) &\geq q_2 \\ \end{aligned}$

which is true since $2q_0 \geq q_2$. Thanks to iMath for this last observation.

In the case of $Z$ being real, I tried mimicking the proof above but the details don't quite work out. In this case, Cauchy-Schwarz still implies that $f_Z(z) \leq 2f_Z(0)$ for all $z$. However, the proof seems to need one more estimation along the lines of $\int_0^1 f_Z(z) dz \geq f_Z(0)$.

Solution 3:

Dinesh, you seem to have the answer (for integer distributions) - need to show $3(q_0+q_1)\geq q_0+q_1+q_2$, ie, $2(q_0+q_1)\geq q_2$, which is true since $2q_0\geq q_i$ for any $i$.