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.

  • 5
    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).2010-12-22
  • 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
    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$.2010-12-24
  • 0
    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, ...).2010-12-24
  • 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