Probabilidad de que todas las bandejas contienen estrictamente más de una pelota?

Question

Aquí está el problema en el que estoy trabajando:

Dado que estoy distribuyendo $N$ bolas en $K$ papeleras, ¿cuál es la probabilidad de que todas las bandejas contienen al menos dos (estrictamente mayor que 1) las pelotas? Esto parece como una pregunta similar a preguntar cuál es la probabilidad de que todas las bandejas contienen estrictamente mayor que cero (por ejemplo, todos están ocupados), pero por alguna razón, es mucho más difícil!

Aunque el problema es similar a esta pregunta relacionada con la dirigida por Henry, Joe, David Mitra, y MJD sobre el número esperado de recipientes que contengan >1 bolas, parece que no puedo aplicar el mismo método desde diferentes ocupación conjuntos de producirse con diferentes probabilidades.

Por ejemplo, la distribución de $N=4$ bolas en $K=2$ contenedores, no se $K^N=16$ total de distribuciones, seis de los cuales tienen dos bolas en cada bin, me da una probabilidad de $6/16$.

Hay una solución general?

Answer 1

La probabilidad es

$$\frac{K!}{K^N} \sum_i (-1)^i \binom{N}{N-i} \left\{ N-i \atop K - i \right\},$$ donde $\left\{ n \atop k \right\}$ es un número de Stirling del segundo tipo.

El $S_2(N,K)$ I tienen debajo de satisfacer $S_2(N,K) = K! \, T(N,K)$ donde $T(n,k)$ es un 2-asociados número de Stirling del segundo tipo. (Ver también sus OEIS entrada.) El $r$asociada a los números de Stirling del segundo tipo son el número de formas de dividir un conjunto de $n$ objetos en $k$ subconjuntos de modo que cada subconjunto contiene, al menos, $r$ objetos. Los subconjuntos pueden ser considerados como indistinguibles de las urnas, por lo que para distinguir multiplicamos por el número de maneras de ordenar de ellos (es decir, $K!$) para obtener $S_2(N,K)$.

Hay una conocida fórmula para el 2 asociada a los números de Stirling del segundo tipo. Es $$T(n,k) = \sum_i (-1)^i \binom{n}{n-i} \left\{ k-i \atop k - i \right\}.$$ Véase, por ejemplo, Fekete, "Dos Notas en la Notación, American Mathematical Monthly 101(8): 1994, pp 771-778. (Mis disculpas por el JSTOR enlace.)

Ya que la probabilidad es $$\frac{S_2(N,K)}{K^N},$$ obtenemos el resultado. Así que mis comentarios a continuación fueron excesivamente pesimista.

---

Respuesta Original:

Constantinos Charalambides la Combinatoria Enumerativa, el Ejercicio 9.23, dice, "Vamos a $S_r(n,k)$ el número de distribuciones de $n$ distinguibles de las pelotas en $k$ distinguibles de las urnas, de modo que cada urna contiene, al menos, $r$ pelotas". El OP está pidiendo $$\frac{S_2(N,K)}{K^N}.$$

Para el $r=2$ de los casos, el ejercicio pide a demostrar la generación de la función $$S_{k,2}(t) = \sum_{n=2k}^{\infty} S_2 (n,k) \frac{t^n}{n!} = \left(e^t-1-t\right)^k.$$

El ejercicio también se da la relación de recurrencia $$\begin{align} S_2(n+1,k) &= k \bigg( S_2(n,k) + n S_2 (n-1, k-1) \bigg), \:\: n \geq 2k, \\ S_2(n,k) &= 0, \:\: n < 2k, \\ S_2(2k,k) &= \frac{(2k)!}{2^k}. \end{align} $$

El hecho de que Charalambides no incluye una expresión explícita no es una buena señal. La generación de la función y la relación de recurrencia puede ser la mejor que se puede esperar (especialmente desde cualquiera de diferenciación de la generación de la función $n$ veces o desenrollar la recurrencia parece que va a ser difícil).

Añadido: El $S_2(N,K)$ números de secuencia A200091 en la OEIS. No hay nada más allá de lo que en el Ejercicio 9.23 en Charalambides del libro.

Answer 2

Yo creo que la siguiente aproximación trabajo. Deje $A$ ser el evento "Hay al menos una bola en cada bin" y $B$ el evento: "Hay al menos dos bolas en cada bin". A continuación,$P(B) = P(A)\cdot P(B|A)$, ya que el $B$ no puede ocurrir sin la $A$.

Parece que ya ha calculado $P(A)$, e $P(B|A)$ se calcula exactamente de la misma manera como $P(A)$, sólo con $N-K$ bolas, puesto que ya hay una bola en cada bin.

Answer 3

Yo creo que simplemente puede empezar por tomar distancia de la $2K$ pelotas que son distribuidos entre los $K$ papeleras y luego se queda con sólo contar el número de maneras de asignar $N-2K$ bolas de a $K$ papeleras. Dividirlo por el número total de maneras de asignar $N$ bolas de a $K$ papeleras y tiene su respuesta, a saber: $$ \frac{K^{N-2K}}{K^N}$$

Answer 4

Esto es equivalente a resolver \begin{equation} x_1 + x_2 + \cdots +x_k = N \end{equation} con $ x_i \ge 2, i=1, \cdots k $ es un entero no negativo. También esto es equivalente a resolver \begin{equation} y_1 + y_2 + \cdots +y_k = N \end{equation} donde$ y_i = x_i + 1.$, esto es equivalente a resolver \begin{equation} x_1 + x_2 + \cdots +x_k = N - k \end{equation} donde $ x_i \ge 1 $. Claramente podemos asumir que $ N-k \ge k $, de lo contrario, la probabilidad es cero. Así, el anwer es $ \binom{N-k-1}{k-1} $ porque cada solución puede ser representado por poner $ k-1 $ trazas entre la $ N-k-1 $ lugares para separar las bolas.

La probabilidad es \begin{equation} \dfrac{\binom{N-k-1}{k-1}}{\binom{N+k}{N}} \end{equation} debido a que el número de maneras de poner $N$ bolas en $k$ papeleras se $\binom{N+k}{N}$ (el número de maneras de poner $N$ bolas y $k$ trazas).

Answer 5

Esta no es realmente una respuesta, sólo un comienzo.

Si $N=2K$, entonces la probabilidad es:

$$\frac{N!}{2^KK^N}=\frac{(2K)!}{(2K^2)^K}$$

cualquier respuesta que no obtener este resultado para $N=2K$ es malo.

Para los restos de esta respuesta, yo uso minúsculas $n,k$.

Deje $S(n,k)=\{(i_1,...,i_k): i_j\geq 0, \sum i_j = n\}$.

A continuación, vamos a $A=\{(i_1,...,i_k)\in S(n,k): \forall j: i_j\geq 2\}$.

Su pregunta es, ¿qué es:

$$\frac{1}{k^n}\sum_{(i_1,...,i_k)\in A}\binom {n}{i_1,...,i_k}$$

Que podría ser una suma para calcular.

Nota, yo estoy usando la multinomial:$$\binom {n}{i_1,...,i_k} = \frac{n!}{i_1!i_2!...i_k!}$$ which is defined for $(i_1,...,i_k)\S(n,k)$.