# Random Variable Inequality

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

-
A bit of motivation/understanding may come from the distribution with 1/n chance of 1.1*i as i ranges from 1 to n and n is large. Ignoring the ends, $Pr[|X-Y|\leq 1]=\frac{1}{n}$ as $X$ and $Y$ have to match, while $Pr[|X-Y|\leq 2]=\frac{3}{n}$ as $X$ and $Y$ just have to be neighboring. So the bound is sharp (assuming it is correct). –  Ross Millikan Dec 22 '10 at 22:31
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. –  Mike Spivey Dec 23 '10 at 17:03

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

-
But that will ruin a good puzzle... –  Yuval Filmus Dec 28 '10 at 8:18

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

-
The form of C.-S. used is the following: let $P$ be the set of all non-negative (infinite) vectors of unit sum. Then for $v \in P$, the vector $u \in P$ maximizing $\sum v_i u_i$ is $v$. –  Yuval Filmus Dec 24 '10 at 1:57
Some counterexamples: Let X, Y independently take on the values {1, ..., N} with uniform probability. In that case $q_0 = 1/N$ and $q_1 = \frac{2N-2}{N^2}$ which is greater than $q_0$ for $N > 3$. For the version of C-S given above, I think you may have confused the $l_2$ norm with the $l_1$ norm. For example you may take $v = (2/3, 1/3, 0, ...)$ in which case the sum is maximized for $u = (1, 0, ...). – eda Dec 24 '10 at 6:22 @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. – Dinesh Dec 24 '10 at 7:07 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\$.

-
Thanks. You are right. That does complete the proof for the integer case. I have edited my answer accordingly. –  Dinesh Dec 24 '10 at 18:43