$n$ bolas en $n+1$ urnas (con una especial urna)

Question

Asumir que no se $n$ bolas numeradas del $1,2,\ldots,n$ $n+1$ urnas, numerado como $0,1,\ldots,n$

Tirar cada bola aleatoriamente en uno de los $n$ urn: urn 1, urna 2, . . . urna $n$. Es decir, cualquier urna excepto urna $0$. (Una bola va a un cierto urna con una probabilidad de $1/n$) cada urna, y si hay más de una bola en una urna, de la que elegir uno al azar y mantener que en esa urna y eliminar las otras bolas y ponerlas en urna $0$.

¿Cuál es la probabilidad de que no se $k$ bolas en la urna 0?

Answer 1

Sugerencias/preguntas guía:

• Cuántas bolas no están en urna $0$?
• Cómo muchas de las urnas $1$ $n$ tuvo pelotas en ellos antes de mover las bolas de la urna $0$?
• ¿Cuál es la probabilidad de que dicha configuración ocurriendo?

Answer 2

El número de bolas en la urna $0$ al final es simplemente el número de urnas numeradas $1$ a través de $n$ que no recibió la pelota durante el balón sacudir el escenario. Deje $K$ ser un conjunto de $k$ de las urnas numeradas $1$ a través de $n$; la distribución de las bolas que deja exactamente las urnas en $K$ vacío es una partición de la $n$ bolas en $n-k$ partes. Hay $n\brace{n-k}$ tal desordenada de las particiones, pero las urnas están numerados, por lo que hay en realidad $(n-k)!{n\brace{n-k}}$ distribuciones dejando exactamente las urnas en $K$ vacía. (Aquí se $n\brace{n-k}$ es un número de Stirling del segundo tipo.) Por lo tanto, hay

$$\binom{n}k(n-k)!{n\brace{n-k}}=\binom{n}k\sum_{i=0}^{n-k}(-1)^{n-k-i}\binom{n-k}ii^n$$

las distribuciones que se traducen en $k$ bolas en la urna $0$. Desde allí se $n^n$ equiprobables distribuciones de la probabilidad de $p_k$ de acabar con $k$ bolas en la urna $0$ es

$$p_k=\frac1{n^n}\binom{n}k(n-k)!{n\brace{n-k}}=\binom{n}k\sum_{i=0}^{n-k}(-1)^{n-k-i}\binom{n-k}i\left(\frac{i}n\right)^n\;.$$

Answer 3

Denotar por $q_r(j)$ la probabilidad de que después de $r\geq0$ lanza exactamente $j\geq0$ urnas están ocupadas. A continuación, $p_0(j)=\delta_{0j}$ y $$q_r(j)={j\over n} q_{r-1}(j)+{n-(j-1)\over n}q_{r-1}(j-1)\qquad(r\geq1)\ .$$ Deje $f_r(j):=n^r q_r(j)$; a continuación, $$f_r(j)=j f_{r-1}(j)+\bigl(n-(j-1)\bigr)f_{r-1}(j-1)\ .$$ Tenga en cuenta que $r$ no aparece en los coeficientes de esta recursividad. Entonces es fácil ver que, de hecho, $$f_r(j)=c_{r,j}\prod_{i=0}^{j-1} (n-i)$$ para las constantes $c_{r,j}$ que satisfacen la recursividad $$c_{r,j}=j c_{r-1,j} + c_{r-1,j-1}\ .$$ Ahora esta es la recursividad de la fórmula de los números de Stirling del segundo tipo, que se denota por a $S(r,j)$ en Stanley combinatoria Enumerativa, vol. I. Uno fácilmente se comprueba que, de hecho,$c_{r,j}=S(r,j)$. Por lo tanto, obtenemos $$q_r(j)={1\over n^r} S(r,j)\prod_{i=0}^{j-1}(n-i)\ .$$ Al final, el número de bolas en ${\rm urn}_0$ es igual al número de desocupados urnas de entre ${\rm urn}_1,\ldots,{\rm urn}_n$. La probabilidad de $p(k)$ que este número es $k$ es el dado por $$p(k)=q_n(n-k)={n!\ S(n,n-k)\over k!\ n^n}\ .$$

Answer 4

El problema que tiene que resolver no es el número de urnas tienen más de una pelota - si usted tiene 12 urnas, 11 de bolas, y 7 urnas bolas en ellos, vas a estar poniendo 4 bolas en la urna 0 no importa lo que el recuento de las bolas en cada urna.

Usted simplemente necesita para calcular la suma de la probabilidad de que, para cada una bola lanzada, si se cae en una urna en la que ya tiene una bola en ella. La primera bola es, obviamente, la probabilidad de $0$, y la posterior bolas se $\frac{k}{n}$ donde $k$ es el número de urnas con bolas en ellos. Para la segunda bola, $k=1$, y para la tercera bola, $k=1+1-\frac{1}{n}$.

La redacción de la pregunta la hace parecer mucho más complicado de lo que es. Este es prácticamente el problema del cumpleaños con un número arbitrario de meses y la gente en la habitación - si dos personas comparten un mes del nacimiento, uno de ellos sale de la habitación (y se pone en una urna - ¡caramba).