Cantidad de números distintos en una secuencia de $k$ números aleatorios en el rango $[1,\ldots,n]$

Question

Sea $D$ la cantidad de números distintos en una secuencia de $k$ números aleatorios en el rango $[1,\ldots,n]$ (n>k). Quiero demostrar que: $D=\Omega(k)$ con alta probabilidad exponencial. Me interesa el caso donde $k/n \rightarrow 0$, por ejemplo, $k=\sqrt{n}$.

Intenté el siguiente enfoque:

$D$ es la cantidad de contenedores no vacíos al lanzar $k$ bolas en $n$ contenedores. $Y$ es la cantidad de contenedores vacios al lanzar $k$ bolas en $n$ contenedores. Entonces, $D=n-Y.

Ahora, utilizando la cota de Chernoff y el hecho de que $\text{E}[Y]=ne^{\frac{-k}{n}}:

$$\begin{align}\Pr(Y>(1+\delta)\text{E}[Y])\le 2^{-\delta \text{E}[Y]}\\ \Pr(D

donde $\delta>2e-1$.

Quiero encontrar $\Pr(D<\beta k)$, pero para hacerlo tengo que tomar $\delta=\frac{n-\beta k-\text{E}[Y]}{\text{E}[Y]}$ que es negativo ya que $\text{E}[Y]\rightarrow n.

¿Qué estoy haciendo mal, o hay alguna otra manera de demostrar que $D=\Omega(k)$ con alta probabilidad exponencial? ¿O tal vez esta afirmación es incorrecta?

¡Gracias!

Answer 1

Así que tengo que tomar $\delta=\frac{n-\beta k-\text{E}[Y]}{\text{E}[Y]}$ que es negativo ya que $\text{E}[Y]\rightarrow\infty$ (primera versión de la pregunta), o $\text{E}[Y]\rightarrow n$ (versión revisada de la pregunta).

No del todo...

• Primero, la media de $Y$ no es lo que has escrito sino $\mathbb E(Y)=n\left(1-\frac1n\right)^k$.
• Segundo, $\delta$ tiene el signo del numerador dividido por $n$, que es $$ \gamma=1-\beta\frac{k}n-\left(1-\frac1n\right)^k. $$ Para cada $\beta\lt1$ fijo, cuando $n\to\infty$ con $k\ll n$, se obtiene $$ \gamma=1-\beta\frac{k}n-\left(1-\frac1n\right)^k. \sim(1-\beta)\frac{k}n, $$ por lo tanto $\gamma\gt0$ para cada $n$ suficientemente grande.

Editar: Se puede controlar la distribución de $D$ de la siguiente manera. Considera el evento $[D\leqslant k-i]$ y elige los $k$ números de forma secuencial. Entonces $D\leqslant k-i$ significa que al menos $i$ veces, se elige un número que ya había sido elegido anteriormente. Esto sucede cada vez con una probabilidad $\leqslant\frac{k}n$ y hay $\binom{k}i\leqslant2^k$ formas de elegir estos $i$ momentos, por lo tanto $\mathbb P(D\leqslant k-i)\leqslant2^k\left(\frac{k}n\right)^i$ $(\ast)$.

Por ejemplo, $\mathbb P(D\leqslant\frac12k)\leqslant\mathrm e^{-\Lambda(n,k)}$ con $\Lambda(n,k)=-\frac12k\log\left(\frac{k}n\right)-k\log2$. Se ve que, si $1\ll k\ll n$, entonces $\Lambda(n,k)\gg k$ por lo tanto el control sobre $\mathbb P(D\leqslant\frac12k)$ es al menos exponencial en $k.

Editar 2: Para ver que $(\ast)$ es cierto, para cada subconjunto $I$ de $\{1,2,\ldots,k\}$ de tamaño $i$, llame $A_I$ al evento en el que en cada momento en $I$ uno elige un número ya elegido anteriormente y en cada momento no en $I$ pero anterior a algún elemento en $I$, se elige un número nuevo (en cada momento no en $I$ después de todo el conjunto $I$, la elección es libre). Luego, los eventos $A_I$ son disjuntos y su unión sobre cada $I$ de tamaño $i$ incluido en $\{1,2,\ldots,k\}$ es $[D\leqslant k-i]$. Hay exactamente ${k\choose i}\leqslant2^k$ conjuntos $I$ de este tipo, y para cada conjunto $I$, $\mathbb P(A_I)\leqslant\left(\frac{k}n\right)^i$. Se sigue el límite superior de $\mathbb P(D\leqslant k-i)$.