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].$$
Puede leer el documento " El teorema 123 y sus extensiones "de Noga Alon y Raphael Yuster.
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)$ .
La forma de C.-S. utilizada es la siguiente: let $P$ sea el conjunto de todos los vectores no negativos (infinitos) de suma unitaria. Entonces para $v \in P$ el vector $u \in P$ maximizar $\sum v_i u_i$ es $v$ .
Algunos contraejemplos: Supongamos que X, Y toman independientemente los valores {1, ..., N} con probabilidad uniforme. En ese caso $q_0 = 1/N$ y $q_1 = \frac{2N-2}{N^2}$ que es mayor que $q_0$ para $N > 3$ . Para la versión de C-S dada anteriormente, creo que puede haber confundido el $l_2$ con la norma $l_1$ norma. Por ejemplo, puede tomar $v = (2/3, 1/3, 0, ...)$ en cuyo caso la suma se maximiza para $u = (1, 0, ...).
@eda: Tienes razón. Todavía podemos aplicar C.S pero cometí un error en el cálculo. Tendremos $q_i \leq 2 q_0$ para todos $i$ (Me faltó el factor de $2$ en el cálculo anterior). Utilizando esto con la estimación anterior se obtiene un límite inferior de $\frac{1}{5}$ ahora. Para fortalecerlo a $\frac{1}{3}$ Sospecho que tendremos que llegar a alguna estimación para $q_1$ en el numerador que actualmente estamos tirando.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
6 votos
Un poco de motivación/comprensión puede venir de la distribución con probabilidad 1/n de 1,1*i cuando i va de 1 a n y n es grande. Ignorando los extremos, $Pr[|X-Y|\leq 1]=\frac{1}{n}$ como $X$ y $Y$ tienen que coincidir, mientras que $Pr[|X-Y|\leq 2]=\frac{3}{n}$ como $X$ y $Y$ sólo tienen que ser vecinos. Así que el límite es nítido (suponiendo que sea correcto).
2 votos
Aunque estoy de acuerdo en que este problema parece sencillo, tiene un (*) al lado en el texto, lo que indica que es más difícil de lo habitual.