¿Por qué es una simulación de un experimento de probabilidad por un factor de 10?

Question

A partir de una universidad de la tarea:

Hay $8$ numerada de las células y $12$ indistinto bolas. Todos los $12$ bolas están divididos al azar entre todos los de la $8$ de las células. ¿Cuál es la probabilidad de que no existe una sola celda vacía ($i.e.$ cada célula tiene al menos $1$ bola)?

La respuesta es $\large\frac{\binom{11}{7}}{\binom{19}{7}}$ que es acerca de $0.0065$. He llegado a este resultado de forma independiente, y fue confirmado por el oficial de la tarea de la solución de la universidad.

Un amigo mío y yo de forma independiente escribió Python simulaciones que ejecutar el experimento muchas veces (probado hasta a $1,000,000$). Hemos utilizado ambos Pitones' generador de números aleatorios y varias listas generadas de forma aleatoria a partir de www.random.org. Los resultados fueron similares, y constantemente se cierne en torno a $0.09$ que es un factor de $10$ o incluso un poco más de los esperado resultado teórico.

Hemos hecho algunas suposiciones equivocadas? Todas las ideas para esta discrepancia?

P. S.: Aquí está el código en Python que me escribió, y tal vez hay alguna defectuosa de la lógica.

def run_test():
    global count, N

    def run_experiment(n_balls, n_cells, offset):
        cells = [0] * n_cells
        # toss balls randomly to cells:
        for j in range(n_balls):
            cells[random.randrange(0, n_cells)] += 1
            # cells[int(lines[offset + j])] += 1
        cells = sorted(cells)
        # print(cells)

        # check if there is an empty cell. if so return 0, otherwise 1:
        if cells[0] == 0:
            return 0
        return 1

    count = 0
    N = 1000000
    offset = 0
    N_CELLS = 8
    N_BALLS = 12
    # iterate experiment
    for i in range(N):
        result = run_experiment(N_BALLS, N_CELLS, offset=offset)
        count += result
        offset += N_CELLS

    print("probability:", count, "/", N, "(~", count / N, ")")

Answer 1

En realidad, usted encontrará que es muy difícil poner las bolas en las células, sin distinguir entre las bolas, sobre todo si quieres igualdad de probabilidades, así como la utilización de métodos de recuento para la simulación. Supongamos que se desea considerar la probabilidad de que todas las bolas se fue en la primera celda: con distinguibles bolas esta probabilidad es $\frac1{8^{12}}$ y es fácilmente simulados aunque poco frecuente; con indistinguible de bolas es $\frac1{19 \choose 7}$ más de un millón de veces más probable, pero difícil de simular

Si las bolas son distinguibles, la probabilidad de todos los ocho cajas llenas es $$\frac{8! \, S_2(12,8)}{8^{12}}$$ where $S_2(n,k)$ is a Stirling number of the second kind and $S_2(12,8)=159027$. That gives a probability that each cell has at least one ball of about $0.0933$. Es esto similar a la simulación?

Si usted realmente quiere simular el indistinguibles bolas caso, a pesar de no ser realista físicamente fuera de Bose–Einstein de condensado a temperaturas cercanas al cero absoluto, puede utilizar una de las estrellas y las barras de analogía. Elija $7$ posiciones distintas para las células de las paredes de las posibles posiciones de $\{0,1,2,3,\ldots,18\}$ para las bolas y las paredes de la célula; un éxito es cuando ninguna de las paredes celulares están en las posiciones $0$ o $18$ y ningún par de ellos son consecutivos

Answer 2

Consideremos el conjunto a$D$ de maneras de distribuir la $12$ bolas etiqueta [abcdefghijkl] entre $8$ celdas numeradas [01234567]. Este conjunto ha $8^{12}\approx7\times10^{10}$ elementos.

Ahora consideremos el conjunto $I$ de distinguir formas para rellenar esos mismos $8$ células [01234567] con $12$ indistinto bolas. Este conjunto ha ${19\choose7}\approx 5\times10^4$ elementos.

La asignación se le pide calcular la probabilidad de un evento a través de la distribución uniforme en $I$, si no en tantas palabras. En principio, se podría aproximar esta probabilidad mediante el muestreo de la distribución uniforme en $I$. Pero su estrategia es la muestra de la distribución uniforme en $D$, y, a continuación, asignar a cada muestra $I$! Que no es el mismo.

En lugar de tomar el promedio de todos los resultados, usted necesita tomar un promedio ponderado, de tal manera que el peso se compensa el número de elementos en $D$ que se asignan a un mismo elemento de $I$. Sugerencia, es algo como esto:

weight = 1
for cell_population in cells:
  weight *= math.factorial(cell_population)

Al menos, que obtiene la respuesta correcta. Rigurosamente justificar esa fórmula como consecuencia de la correlación entre la $D$ e $I$ se deja como ejercicio para el lector.

Answer 3

El problema original se plantea, por lo que puedo decir, para mostrar la diferencia entre las combinaciones y permutaciones. En la naturaleza, no hay tal cosa como bolas indistinguibles. Semi-infinita de pruebas (por ejemplo, de Las Vegas) han demostrado que esto es cierto.

Ahora, si el problema realmente quiere que usted use "indistinguible" bolas a los fines de resolver el problema, entonces sí, usted necesita usar combinaciones y no permutaciones cuando el cálculo de todas las formas en que la indistinguibles bolas se colocan en los contenedores. Y, por supuesto, usted necesita usar permutaciones de las bolas numeradas, como son distinguibles el uno del otro y de la colección de bolas indistinguibles.

Ahora, yo creo que Chris Culter cálculos de reflejar esta diferencia. Si el código de Python hace esto correctamente, no podemos decir hasta que veamos el código.