Cubos de Bolas, ¿Se llenará uno si añado otra Bola?

Question

Fui referido aquí por stackoverflow.com. Con un poco de búsqueda he encontrado esto: otra pregunta sobre bolas y papeleras pero no es exactamente lo que busco. Más bien lo contrario. Es decir, el número esperado de cubos que tienen H-1 bolas en ellos.

Me doy cuenta de que el título es un poco impar. Pero este es un problema de estadística/probabilidad que estoy tratando de resolver, pero estoy perplejo. (No, no, no es tarea, ver la parte inferior de la explicación real)

La premisa es sencilla. Tienes N cubos. Cada cubo puede contener H bolas. Ninguno de los cubos está lleno. Ya tienes D bolas en los cubos, pero no sabes dónde están las bolas (¡te has olvidado!) Eliges un cubo al azar para añadir 1 bola. ¿Cuál es la probabilidad de que ese cubo esté lleno?

Algunos ejemplos de diagramas posibles, con N = 4, H = 3, D = 4. Cada caso es sólo una disposición hipotética de las bolas. para uno de los muchos casos.

Scenario 1: 1 bucket could be filled.
|   |   |   |   |
+ - + - + - + - +
| B |   |   |   |
+ - + - + - + - +
| B | B |   | B |
+ - + - + - + - +

Scenario 2: 2 buckets could be filled.
|   |   |   |   |
+ - + - + - + - +
|   | B | B |   |
+ - + - + - + - +
|   | B | B |   |
+ - + - + - + - +

Scenario 3: 0 buckets could be filled.
|   |   |   |   |
+ - + - + - + - +
|   |   |   |   |
+ - + - + - + - +
| B | B | B | B |
+ - + - + - + - +

El problema es que necesito una ecuación de propósito general en la forma de P = f(N, H, D)

---

Muy bien, has sintonizado hasta aquí. La razón detrás de esta consulta sobre matemáticas, es que tengo curiosidad en tener grandes batallas entre unidades. Cada unidad podría pertenecer a una brigada que contiene muchas unidades del mismo tipo. sin embargo, la batalla progresará lentamente en el tiempo. En cada fase de la batalla, el estado se guardará en la BD. En lugar de guardar cada unidad y la salud de cada unidad, quiero guardar el número de unidades y el daño total de la brigada. Cuando se añade daño a una brigada, se ejecuta la función f(N, H, D) y devuelve un % de probabilidad de que una unidad de la brigada sea destruida (todos sus PV se han consumido). Esto entonces elimina esa unidad de la brigada disminuyendo N en 1 y D en H.

Antes de ponerme demasiado técnico, necesito aplicar esta solución a un programa. Así que las integrales están fuera de la cuestión por ahora. Estoy atascado con álgebra y funciones trigonométricas.

Agradezco la ayuda

Answer 1

La salida se ha modificado sustancialmente a raíz de los comentarios de Matt, lo que afecta al resultado.

Sea $f(N,H,D)$ sea el número de formas de poner $D$ bolas en $N$ cubos en los que haya estrictamente menos de $H$ bolas en cada cubo, y contando los distintos órdenes de las bolas como distintos (es decir, bolas etiquetadas y cubos etiquetados). Podemos calcular esto con la recurrencia

$$f(N,H,D) = \sum_{i=0}^{H-1} {D \choose i} f(N-1,H,D-i)$$

empezando por $f(0,H,D)=0$ excepto $f(0,H,0)=1$ y recordando ${x \choose y} = 0$ si $x<y$ . Esto se debe a la adición de un cubo adicional y poner de $0$ a $H-1$ bolas en él, en un orden mezclado con las bolas de los otros cubos. Por ejemplo $f(4,3,4)=204$ .

¿Cuántos de ellos han $H-1$ bolas en la primera papelera? Eso es como quitar $H-1$ bolas y una papelera, por lo que es $f(N-1,H,D-H+1) {D \choose H-1}$ que en el ejemplo es $9 \times {4 \choose 2} = 54$ .

Así pues, la probabilidad de que (a) coloque la siguiente bola en el primer cubo y (b) llene el primer cubo al hacerlo es $\frac{1}{D} \cdot \frac{f(N-1,H,D-H+1) {D \choose H-1}}{f(N,H,D)}$ por lo que la probabilidad de llenar cualquiera de los contenedores con la siguiente bola es $D$ veces, es decir

$$\frac{f(N-1,H,D-H+1) {D \choose H-1}}{f(N,H,D)}$$

o en este ejemplo $\dfrac{54}{204} = \dfrac{9}{34}$ confirmando el resultado de Matt.

Answer 2

Así es como yo lo veo. En su caso de ejemplo de N, H, D = 4, 3, 4 :

{2,2,0,0}   {6,  6}
{2,1,1,0}   {12,12}
{1,1,1,1}   {1, 24}

A la izquierda tenemos particiones restringidas, a la derecha el número de formas de permutar y llenar de forma única cada partición.

Por lo tanto, tenemos una enumeración combinada de:

{2,2,0,0}     36
{2,1,1,0}    144
{1,1,1,1}     24

Cuento el número de contenedores casi llenos como 2 * 36 + 144 = 216 fuera de 4 * (36 + 144 + 24) = 816 para una probabilidad de 216/816 = 9/34 .

En otras palabras, obtengo el mismo resultado que Matt.