Dado $n$ variables aleatorias $X_1,...,X_n$ elegidos de manera uniforme e independiente entre $\{1,...,n\}$ quiero demostrar que para cada constante $c$ con probabilidad $1-o(1)$ (cuando $n$ crece) habrá $c$ variables aleatorias con el mismo valor (para $c=2$ es un problema de cumpleaños).
Lo que he intentado es definir, para cada subconjunto de tamaño $c$ de las variables un indicador $Y_i$ que equivale a $1$ si todos los valores del subconjunto son iguales. Se cumple que: $$Pr(Y_i = 1) = \frac{1}{n^{c-1}} $$ Más tarde, definí $Y = \sum Y_i$ y se observa que : $$E[Y] = {n \choose c} \frac{1}{n^{c-1}} $$ que va claramente por encima de $1$ cuando $n$ se hace lo suficientemente grande.
Creía que el siguiente paso sería acotar la probabilidad de que $Y$ está lejos de su expectativa (utilizando, por ejemplo, el límite de Chernoff). La cuestión es que el $Y_i$ s son dependientes entre sí (por ejemplo, dos indicadores de este tipo con sólo una variable diferente entre ellos: saber que un indicador es $0$ implica que el otro es $0$ también), por lo que es un problema utilizar ese tipo de límites. ¿Alguna idea sobre cómo proceder?
Respuesta
¿Demasiados anuncios?
Esto puede hacerse utilizando Chebyshev: acotar la varianza y demostrar que no es demasiado mayor que la media. A continuación, $P(Y=0)\leq\text{Var}(Y)/E(Y)^2$ .
Ahora cuando una variable cuenta el número de eventos en algún conjunto $A$ que se producen, como ésta, se puede expresar la varianza como $$\text{Var}(Y)=\sum_{a,b\in A}(P(a,b)-P(a)P(b)).$$ Aquí todos los términos donde $a$ y $b$ implican $c$ -tuplas (o pares que se solapan exactamente en un lugar) son eventos independientes y contribuyen $0$ a esta suma. Si se solapan en $d$ lugares, donde $2\leq d\leq c$ entonces el caso de que $a$ y $b$ ocurre es el caso de que algún $2c-d$ de la $X_i$ son iguales. Cada grupo de $2c-d$ se cuenta $\binom{2c-d}{d}\binom{2c-2d}{c-d}$ veces (el número de maneras de elegir el solapamiento y luego dividir el resto en dos grupos iguales) - no importa cuál sea este número, ya que no depende de $n$ . Por tanto, la contribución de estos pares es $$\binom{2c-d}{d}\binom{2c-2d}{c-d}\binom{n}{2c-d}\bigg(\frac1{n^{2c-d-1}}-\frac1{n^{2c-2}}\bigg).$$ Esto es de orden $n$ para cada $d$ . Para fijos $c$ hay un número constante de opciones para $d$ por lo que la varianza es $\Theta(n)$ . Dado que la media también es $\Theta(n)$ es suficiente.
