Con $n$ bolas y $n$ papeleras, ¿cuál es la probabilidad de que exactamente $k$ papeleras tienen exactamente $1$ pelota?

Question

Tengo las bolas y cubos de problema. Supongamos que yo tiro $n$ bolas uniformemente al azar en $n$ papeleras. ¿Cuál es la probabilidad de que exactamente $k$ papeleras de terminar con exactamente $1$ pelota?

Sé que esto parece un problema clásico y puede parecer "simple" o "ingenuo", pero he trabajado días y todavía no puede obtener la respuesta.

Sin embargo, creo que tengo una buena aproximación. Es decir, vamos a $X$ denotar el número de contenedores. Entonces

$$ Pr(X=k) \approx \binom{n}{k}\left(\frac{1}{e}\right)^{k}\left(1-\frac{1}{e}\right)^{n-k} $$

donde $1/e$ es una aproximación para $(1-1/n)^{n-1}$.

Esta aproximación funciona muy bien cuando se $n$ es grande y mal al $n$ es pequeña (como $n<5$).

De todos modos, estoy en busca de una expresión exacta. Alguien tiene una idea?

Pd: he escrito una simulación simple en C++; puedes comprobar tu respuesta con lo primero: Simulación de Código Aquí.

Answer 1

Fórmula exacta se puede obtener el uso de de Moivre la fórmula para la ocurrencia de exactamente $k$ intercambiables eventos:

$$ p_n(k) = \binom{n}{k} \sum_{i=k}^n (-1)^{i-k} \binom{n-k}{i-k} \mathbb{P}(A_1 \ldots A_i) $$

Aquí $A_1$ es el evento de que el primer bin contiene $1$ bola, $A_1 A_2$ es el evento de que los dos primeros contenedores de cada una contiene 1 bola y así sucesivamente.

$$ \begin{eqnarray} \mathbb{P}(A_1) &=& \binom{n}{1} \frac{1}{n} \left( 1 - \frac{1}{n} \right)^{n-1} = \left( 1 - \frac{1}{n} \right)^{n-1} \\ \mathbb{P}(A_1 A_2) &=& \binom{n}{1,1,n-2} \frac{1}{n^2} \left( 1- \frac{2}{n} \right)^{n-2} = \frac{n-1}{n} \left( 1- \frac{2}{n} \right)^{n-2} \\ \mathbb{P}(A_1 \ldots A_i) &=& \binom{n}{i} i! \frac{1}{n^i} \left( 1 - \frac{i}{n} \right)^{n-i} \end{eqnarray} $$

Por lo tanto el resultado exacto que buscamos es: $$ p_n(k) = \binom{n}{k} \sum_{i=k}^n (-1)^{i-k} \binom{n-k}{i-k} \binom{n}{i} i! \frac{1}{n^i} \left( 1 - \frac{i}{n} \right)^{n-i} $$

Esto está de acuerdo con las simulaciones.

Answer 2

Deje $S_i$ el conjunto de resultados con $1$ pelota en el recipiente $i$. Deje $N_j$ el número de resultados en las intersecciones de $j$ de la $S_i$; por ejemplo,$N_3=\sum_{i<j<k}|S_i\cap S_j\cap S_k|$. Hay $\binom{n}{j}$ opciones de la $S_i$ a se cruzan, para cada elección de $S_i$, $\binom{n}{j}j!$ opciones y órdenes de bolas para poner en los $j$ papeleras, y $(n-j)^{n-j}$ formas de organizar el otro $n-j$ bolas en el otro $n-j$ papeleras. Por lo tanto, $$ N_j=\binom{n}{j}\binom{n}{j}j!(n-j)^{n-j} $$ Desde allí se $n^n$ resultados posibles, para calcular la probabilidad de obtener exactamente $k$ contenedores con $1$ pelota, el uso Generalizado de la Inclusión-Exclusión en el Principio: $$ \begin{align} \frac{1}{n^n}\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}N_j &=\frac{1}{n^n}\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}\binom{n}{j}\binom{n}{j}j!(n-j)^{n-j}\tag{1}\\ &=\frac{1}{n^n}\sum_{j=k}^n(-1)^{j-k}\binom{n}{k}\binom{n-k}{n-j}\frac{n!}{(n-j)!}(n-j)^{n-j}\\ &=\binom{n}{k}\frac{n!}{n^n}\sum_{j=k}^n(-1)^{j-k}\binom{n-k}{n-j}\frac{(n-j)^{n-j}}{(n-j)!}\\ &=\binom{n}{k}\frac{n!}{n^n}\sum_{j=0}^{n-k}(-1)^{n-k-j}\binom{n-k}{j}\frac{j^j}{j!} \end{align} $$ Apéndice:

Para comprobar que las probabilidades de las $k=0,1,\dots,n$ total a $1$, $(1)$ se puede sintetizar de manera bastante sencilla en $k$: $$ \begin{align} &\sum_{k=0}^n\frac{1}{n^n}\sum_{j=k}^n(-1)^{j-k}\binom{j}{k}\binom{n}{j}\binom{n}{j}j!(n-j)^{n-j}\\ &=\frac{1}{n^n}\sum_{j=0}^n\sum_{k=0}^j(-1)^{j-k}\binom{j}{k}\binom{n}{j}\binom{n}{j}j!(n-j)^{n-j}\\ &=\frac{1}{n^n}\sum_{j=0}^n(-1)^{j}0^j\binom{n}{j}\binom{n}{j}j!(n-j)^{n-j}\\ &=\frac{1}{n^n}(-1)^00^0\binom{n}{0}\binom{n}{0}0!(n-0)^{n-0}\\ &=1 \end{align} $$ Mathematica:

Aquí es la trama de $80$ bandejas, que coincide con Sasha de la parcela:

Answer 3

No estoy seguro acerca de lo que te estoy diciendo, pero tal vez esto podría ser cierta :

Contar el número de posibilidades que da lugar a la $X \ge k$. Usted tiene que elegir los que las papeleras de obtener $1$ pelota, y entonces usted tiene que elegir el que las bolas de obtener en los contenedores. Esto le da a usted $\begin{pmatrix} n \\ k \end{pmatrix}\begin{pmatrix} n \\ k \end{pmatrix}$ posibilidades. EDITAR porque de un buen comentario =) : también tienes Que elegir aquí que la bola va en que bin, por tanto, un factor adicional de $k!$.

Ahora el resto de $n-k$ pelotas de ir a cualquier lugar en el $n-k$ papeleras de la izquierda, por lo que le da un factor adicional de $(n-k)^{n-k}$. El número total de posibilidades es sólo $n^n$, por lo tanto $$ \mathbb P(X\ge k) = \frac{ \begin{pmatrix} n \\ k \end{pmatrix}\begin{pmatrix} n \\ k \end{pmatrix} k! (n-k)^{n-k} }{n^n}. $$ Para obtener $\mathbb P(X=k)$, sólo calcular $\mathbb P(X \ge k) - \mathbb P(X \ge {k+1})$.

No sé si nuestras fórmulas son asintóticamente equivalentes (el tuyo y el mío), pero tal vez si usted está más interesado en esta cuestión de lo que soy, usted podría tratar de trabajar. =)

Espero que ayude,

P. S. Después de leer los comentarios de mi argumento se siente mal, pero todavía voy a salir de allí para los lectores.