30
$\begingroup$

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]$.

Thanks for your time.

  • 2
    While I agree that this problem seems simple, it does have a (*) by it in the text, indicating that it is more difficult than usual.2010-12-23

3 Answers 3

6

You may read the paper "123 theorem and its extensions" by Noga Alon

  • 3
    But that will ruin a good puzzle...2010-12-28
3

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)$.

  • 0
    @eda: You are right. We can still apply C.S but I made a mistake in the calculation. We will have $q_i \leq 2 q_0$ for all $i$ (I missed the factor of $2$ in the above calculation). Using this with the above estimate gives a lower bound of $\frac{1}{5}$ now. To strengthen it to $\frac{1}{3}$, I suspect we will need to come up with some estimate for $q_1$ in the numerator which we are currently throwing away.2010-12-24
2

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

  • 0
    Thanks. You are right. That does complete the proof for the integer case. I have edited my answer accordingly.2010-12-24