Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
1  
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
add comment

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
2  
But that will ruin a good puzzle... –  Yuval Filmus Dec 28 '10 at 8:18
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.