Ejercicio 1.6.3 de *El método probabilístico* de Alon y Spencer: demuestre que $Pr[|X-Y| \leq 2] \leq 3 Pr[|X-Y| \leq 1]$ para VR reales i.i.d. $X$ y $Y$

Question

Leyendo un poco durante el descanso ( El método probabilístico de Alon y Spencer); no se le ocurre la solución para este resultado aparentemente sencillo (¿y quizá incluso un poco sorprendente?):

(A-S 1.6.3) Demuestre que para cada dos variables aleatorias reales independientes idénticamente distribuidas $X$ y $Y$ , $$Pr[|X-Y| \leq 2] \leq 3 Pr[|X-Y| \leq 1].$$

Answer 1

Puede leer el documento " El teorema 123 y sus extensiones "de Noga Alon y Raphael Yuster.

Answer 2

Puedo probarlo para el caso en que $Z = |X-Y|$ sólo toma valores enteros.

Sea $q_i = P(Z=i)$ para $i=0,1,\dots$ . Entonces, tenemos que demostrar que $\frac{q_0+q_1}{q_0+q_1+q_2} \geq \frac{1}{3}$ . Esto se deduce de la observación de que $2q_0 \geq q_i$ para todos $i$ . Esto se deduce de la desigualdad de Cauchy Schwarz. Entonces,

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

lo que es cierto ya que $2q_0 \geq q_2$ . Gracias a iMath por esta última observación.

En el caso de $Z$ siendo real, he intentado imitar la prueba anterior pero los detalles no me salen del todo bien. En este caso, Cauchy-Schwarz sigue implicando que $f_Z(z) \leq 2f_Z(0)$ para todos $z$ . Sin embargo, la prueba parece necesitar una estimación más del tipo $\int_0^1 f_Z(z) dz \geq f_Z(0)$ .

Answer 3

Dinesh, parece que tienes la respuesta (para distribuciones enteras) - necesitas mostrar $3(q_0+q_1)\geq q_0+q_1+q_2$ es decir, $2(q_0+q_1)\geq q_2$ lo que es cierto ya que $2q_0\geq q_i$ para cualquier $i$ .