Hallazgo: El número esperado de urnas que están vacías

Question

Un total de $n$ bolas, numeradas $1$ a través de $n$ se ponen en $n$ urnas, también numeradas $1$ a través de $n$ de tal manera que la pelota $i$ tiene la misma probabilidad de ir a cualquiera de los urnas $1, 2, . . . , i$ . Encuentra el número esperado de urnas que están vacías.

¿Puede alguien ayudarme? No entiendo.

Muchas gracias.

Answer 1

Procedemos por inducción. Para el caso $n=1$ es evidente que el valor esperado de las urnas vacías es $0$ . Ahora, supongamos que con $n$ ue nuestro valor esperado, $E(n)$ viene dada por $(n-1)/2$ .

Para el caso $n+1$ podemos pensar en nuestro procedimiento en dos pasos:

1. Lugar $n$ bolas (según la regla para $n$ bolas) en la primera $n$ urnas.
2. Coloca una bola en cualquier urna.

Después del paso 1, hay una media de $E(n)+1$ urnas vacías. Como la última bola acabará en cualquier ón con igual probabilidad, hay una probabilidad de $(E(n)+1)/(n+1)$ que nuestra última bola caerá en una urna vacía. Restando, queda un $(n-E(n))/(n+1)$ probabilidad de que la última bola caiga en una urna previamente ocupada. Es decir, nuestro valor esperado en las urnas vacías viene dado por

$$E(n+1)=E(n) \left(\frac{E(n)+1}{n+1}\right)+(E(n)+1)\left(\frac{n-E(n)}{n+1}\right)=\frac{n-1}{2}\cdot \frac{1}{2} + \frac{n+1}{2}\cdot \frac{1}{2},$$ en la que hemos utilizado la hipótesis inductiva $E(n)=(n-1)/2$ . El lado derecho de la expresión anterior es $n/2$ y esto demuestra la $n+1$ caso (por lo que concluimos por inducción).

Me gustaría señalar que no habría sabido formular esta inducción sin hacer algunos casos a mano. Me di cuenta de que este patrón se mantuvo para $n \leq 4$ antes de intentar la prueba que ves arriba.

Answer 2

Dejemos que $X$ sea el número de urnas vacías. Entonces $X=X_1+X_2+\dots+X_n$ donde $X_i$ es la variable indicadora cuyo valor es $1$ si el $i$ La urna está vacía, $0$ de lo contrario. Entonces $E(X_i)$ es la probabilidad de que el $i$ La urna está vacía, es decir, $E(X_i)=\frac{i-1}{i}\frac{i}{i+1}\frac{i+1}{i+2}\dots\frac{n-1}{n}=\frac{i-1}{n}$ (producto telescópico). Por linealidad de la expectativa, $$E(X)=E(X_1)+\dots+E(X_n)=\frac{0}{n}+\frac{1}{n}+\frac{2}{n}+\dots+\frac{n-1}{n}=\frac{{n\choose 2}}{n}=\frac{n-1}{2}.$$