Encontrar el número esperado de valores distintos seleccionados de un conjunto de enteros

Question

Tengo un conjunto de $n$ enteros $\{1, . . . , n\}$ y selecciono tres valores con reemplazo. Cómo puedo encontrar el número esperado de valores distintos?

Obsérvese que cada valor se elige de manera uniforme e independiente.

Answer 1

Primero respondemos a la pregunta exacta planteada, en la que se extraen tres elementos, y luego presentamos un enfoque más potente que resuelve el caso más general en el que se extrae cualquier número de elementos.

---

La probabilidad de que el primer elemento no haya sido elegido antes es $1$ . La probabilidad de que el segundo elemento no haya sido elegido antes es $\frac{n-1}n$ . La probabilidad de que el tercer elemento no haya sido elegido antes es $\frac{n-2}n$ si los dos primeros elementos son diferentes y $\frac{n-1}n$ si los dos primeros elementos coinciden. Los dos primeros elementos son diferentes con probabilidad $\frac{n-1}n$ y coinciden con la probabilidad $\frac{1}n$ . Por lo tanto, el número esperado de elementos distintos es $$ 1+\frac{n-1}n+\frac{n-2}n\times\frac{n-1}n+\frac{n-1}n\times\frac1n=\frac{3n^2-3n+1}{n^2} $$

---

De manera más general, considere el número $N_k$ de diferentes artículos elegidos después de $k$ picos. Entonces $N_0=0$ casi seguro y, sabiendo $N_k$ la probabilidad de elegir un nuevo artículo en el momento $k+1$ es $(n-N_k)/n$ por lo que $$\mathrm E(N_{k+1}\mid N_k)=N_k+\frac{n-N_k}n\qquad\text{almost surely}$$ Esto muestra que el número esperado de artículos diferentes después de $k$ elige $\mathrm E(N_k)$ es tal que $\mathrm E(N_0)=0$ y $$\mathrm E(N_{k+1})=\mathrm E(N_k)+\frac{n-\mathrm E(N_k)}n=1+a_n\mathrm E(N_k)$$ por cada $k\geqslant0$ con $$a_n=1-\frac1n$$ Así, para cada $k\geqslant0$ , $$\mathrm E(N_k)=\frac{1-a_n^k}{1-a_n}$$ o, de forma equivalente, $$ \mathrm E(N_k)=n\,\frac{n^k-(n-1)^k}{n^{k}}=\sum\limits_{i=0}^{k-1}(-1)^{i}{k\choose i+1}\frac1{n^i} $$ Por ejemplo, la quinta fila del triángulo de Pascal dice $$1\quad5\quad10\quad10\quad5\quad1$$ por lo que $$E(N_5)=\frac{5n^4-10n^3+10n^2-5n+1}{n^5}$$

Answer 2

El método de @Did utiliza muy bien la recursión para llegar al número esperado. Yo llegué a la misma respuesta usando cálculos más mundanos.

Generalicemos escogiendo $p$ números de $1\dots n$ con sustitución. Calculemos la probabilidad de elegir $d$ números distintos. Elija uno de los $\binom{n}{d}$ conjuntos de $d$ números distintos. La probabilidad de seleccionar todos los $p$ elige entre esos $d$ números distintos es $\left(\frac{d}{n}\right)^p$ . Sin embargo, esto también cuenta los casos en los que algunos de los $d$ los números no fueron elegidos. La inclusión-exclusión dice que la probabilidad de escoger todos esos $d$ es $$ \sum_k(-1)^{k}\binom{d}{d-k}\left(\frac{d-k}{n}\right)^p=\sum_k(-1)^{d-k}\binom{d}{k}\left(\frac{k}{n}\right)^p\tag{1} $$ Por lo tanto, la probabilidad de elegir exactamente $d$ elementos distintos es $\binom{n}{d}$ veces $(1)$ . Por lo tanto, el valor esperado es $$ \begin{align} &\sum_d\sum_k(-1)^{d-k}d\binom{n}{d}\binom{d}{k}\left(\frac{k}{n}\right)^p\\ &=\sum_d\sum_k(-1)^{d-k}d\binom{n}{k}\binom{n-k}{n-d}\left(\frac{k}{n}\right)^p\\ &=n-\sum_d\sum_k(-1)^{d-k}(n-d)\binom{n}{k}\binom{n-k}{n-d}\left(\frac{k}{n}\right)^p\\ &=n-\sum_d\sum_k(-1)^{d-k}(n-k)\binom{n}{k}\binom{n-k-1}{n-d-1}\left(\frac{k}{n}\right)^p\\ &=n-\sum_k(n-k)\binom{n}{k}\delta(k-n-1)\left(\frac{k}{n}\right)^p\\ &=n-n\left(\frac{n-1}{n}\right)^p\\ &=n\left(1-\left(\frac{n-1}{n}\right)^p\right)\tag{2} \end{align} $$

Answer 3

Me gustaría dar un simple razonamiento al respecto.

Supongamos que tenemos un SRS de tamaño p seleccionado de una población de tamaño n con reemplazo. Para encontrar el número esperado de elementos únicos en la muestra, hacemos uso de la linealidad de la expectativa.

Sea X: número de elementos únicos en p picos Sea Xi: Indicador de que i es un elemento único

Entonces, X = ∑Xi ,

Donde Xi=1, si i es seleccionado en p picks y Xi=0, en caso contrario

Entonces,E(X) = ∑E(Xi) = ∑P(i es seleccionado en p picks) = ∑(1-P(i no es seleccionado en p picks)) = ∑(1-((n-1)/n)^p)= n(1-((n-1)/n)^p)

Nota: Aquí, todas las selecciones son independientes (SRSWR)