Número esperado de llamadas para ganar bingo

Como lo demuestran algunas de mis respuestas anteriores, me gusta escribir simulaciones numéricas rápidas si parecen factibles. Bingo parece especialmente fácil (código de Python a continuación).

No estoy seguro de si esto es cierto, pero creo que los cartones de bingo son esencialmente independientes entre sí. Es decir, si podemos calcular la distribución de probabilidad de un solo jugador$N=1$duración del juego, podemos usar eso para calcular las probabilidades conjuntas para cualquier número de jugadores.

Lo que obtengo parece coincidir con su experiencia de juego, la duración media del juego para un solo jugador fue$42.4$con una desviación estándar de$9.6$. Hay un ligero sesgo en el PDF hacia juegos más largos. El PDF completo se muestra a continuación:

from numpy import *
from collections import Counter

def new_board():
    cols = arange(1,76).reshape(5,15)
    return array([random.permutation(c)[:5] for c in cols])

def new_game():
    for token in random.permutation(arange(1,76)):
        yield token

def winning(B):
    if (B.sum(axis=0)==5).any(): return True
    if (B.sum(axis=1)==5).any(): return True
    if trace(B)==5 or trace(B.T)==5: return True
    return False

def game_length(board, game):
    B = zeros((5,5),dtype=bool)
    B[2,2] = True
    for n,idx in enumerate(game):
        if winning(B): return n
        B[board==idx] = True

def simulation(trials):
    C = Counter()
    b = new_board()
    for _ in xrange(trials):
        C[game_length(b, new_game())] += 1
    return C

repeats = 10**2
trials  = 10**3

from multiprocessing import *
P = Pool()
sol = sum(P.map(simulation,[trials,]*repeats))
P.close()
P.join()

X = array(sorted(sol.keys()))
Y = array([float(sol[x]) for x in X])
Y/= repeats*trials

EX = array(list(sol.elements()))
print "Mean and stddev", EX.mean(), EX.std()

import pylab as plt
plt.fill_between(X, Y, lw=2, alpha=.8)

plt.plot([EX.mean(),EX.mean()], [0,1.2*max(Y)], 'r--',lw=2)
plt.ylim(ymax = 1.2*max(Y))
plt.xlabel("Expected game length")

plt.show()

Gracias por la pregunta y la respuesta. A mediados de la década de 1980, pasé mucho tiempo simulando distribuciones con FORTAN e IMSL. Hace unos días, pasé unas horas jugando bingo, no el juego estadounidense descrito por Ron, sino la versión del Reino Unido que tiene (en la versión que jugué) dígitos 1-90 dispuestos en 6 'juegos' en una página - 15 dígitos en cada 'juego' - dispuestos en 3 filas de 9 (incluidos los espacios en blanco). Se usaron los 90 dígitos y cada uno de los 6 juegos en la página era único pero no independiente. Alrededor de 50 jugadores en la sala, cada uno tenía una hoja con 6 juegos. La página de cada jugador era única y probablemente independiente. Se cantaban números aleatorios hasta que un jugador tenía los 15 en uno de sus 6 juegos. Durante la tarde, el proceso se repitió unas 14 veces, cada vez con hojas nuevas. (Las hojas habían sido encuadernadas en pequeños folletos.) Durante la tarde, nos dimos cuenta de que el número de dígitos llamados antes del bingo era alto 60s. ¿Cuál fue la distribución real? Estoy tratando de entender cómo Python decidió simular el juego de bingo.

Encontré este sitio https://github.com/gvenkat/bingocards que me mostró cómo generar las tarjetas de bingo que se utilizan. Agregué a ese código un par de bucles para generar la simulación. Primero genera números aleatorios para llamar.

nums1_90 = list(range(1,91))
random.shuffle(nums1_90)

Luego, cambie la forma de la lista del 'diseño' de la hoja de bingo para poner cada lista de juegos (6 conjuntos de 3 filas y 9 columnas) en su propia sublista (27 de largo)

arcillaout = np.reshape(alayout,(num_rows,27), order='A')

Luego, recorra la lista nums1_90 y establezca cualquier dígito coincidente en Clayout en cero. Salir (con contador) si la suma de cualquier sublista es cero.

for idx, n in enumerate(nums1_90, 1): 
    for i in range( num_rows  ):
        for j in range( 27 ):
            number = clayout[ i ][ j ]
            if(n == number):
               clayout[ i ][ j ] = 0
    csum = [sum(clayout[ii]) for ii in range(num_rows)] 
    if (0 in csum):
        last = idx
        break

Ejecute la simulación 100.000 veces. Esto representa 1 jugador jugando 100,000 juegos. El pdf está sesgado (similar a Hooked arriba) y se ve un poco venenoso.

¿Qué sucede para diferentes números de jugadores? Ejecuté la simulación 100 veces para aumentar el número de jugadores de 1 a 50. A continuación se muestra el mínimo, la media, la mediana y el máximo para un número creciente de jugadores. El pdf mantiene su forma y cambia rápidamente desde un centro de 70 altos y luego de manera constante hasta un centro de 60 medios. El valor de muestra máximo está limitado por la cola corta de ese lado, pero el valor de muestra mínimo muestra una gran variabilidad debido a la cola larga.

Números llamados antes de 'Bingo' con un número creciente de jugadores

Inspirándome en la respuesta de Hooked, modifiqué su guión para calcular el número esperado de bolas extraídas para determinar algún ganador en el bingo de apagón, en un juego de un cierto número de cartones. El código se modifica para ejecutarse en Python 3 y no requiere el módulo matlibplot para ejecutarse.

Para una carta, el número de bolas es sorprendentemente grande, pero esto tiene una explicación sencilla. ¡Solo considere la última bola extraída de las 75, hay aproximadamente 1/3 de probabilidad de que la tarjeta tenga ese número, por lo que un tercio de las cartas no se bloqueará hasta que se extraigan todas las bolas!

Las probabilidades se vuelven más complicadas cuando el juego tiene muchas cartas. Generalmente, cuantas más cartas hay en el juego, menos bolas se necesitan. Para un juego de tamaño razonable, la cantidad de bolas es de aproximadamente 60 de 75.

from numpy import *
from collections import Counter
from multiprocessing import *

def new_board():
    cols = arange(1,76).reshape(5,15)
    return array([random.permutation(c)[:5] for c in cols])

def new_game():
    for token in random.permutation(arange(1,76)):
        yield token

def winning(B):
    #if (B.sum(axis=0)==5).any(): return True
    #if (B.sum(axis=1)==5).any(): return True
    #if trace(B)==5 or trace(B.T)==5: return True
    if B.sum()==25: return True  ## blackout
    return False

def game_length(board, game):
    B = zeros((5,5),dtype=bool)
    B[2,2] = True
    for n,idx in enumerate(game, 1):
        B[board==idx] = True
        if winning(B): return n

def simulation(trials):
    C = Counter()
    b = new_board()
    for _ in range(trials):
        C[game_length(b, new_game())] += 1
    return C

if __name__ == '__main__':
    repeats = 10**2
    trials  = 10**3
    numBoards = 500

    P = Pool()
    sol = sum(P.map(simulation,[trials,]*repeats))
    P.close()
    P.join()

    X = array(sorted(filter(None, sol.keys())))
    Y = array([sol[x] for x in X])
    cumY = cumsum(Y)
    probnotwon1board = [(float(repeats*trials - y)/(repeats*trials)) for y in cumY]
    probnotwonanyboard = [x**numBoards for x in probnotwon1board]
    probsomeboardwon = [1 - x for x in probnotwonanyboard]

    print("Number of boards: ", numBoards)
    print()
    print("Ball  Winners Cumulative  Prob 1 Board    Prob No   Prob Some")
    print("               Winners      Not Won      Board Won  Board Won")
    print()
    for i in range(len(X)):
        print(" {0:2d}   {1:6d}   {2:6d}       {3:1.6f}     {4:1.6f}    {5:1.6f} ".format(X[i], Y[i], cumY[i], probnotwon1board[i], probnotwonanyboard[i], probsomeboardwon[i]))
    print()

Vuelve una ejecución de muestra

Number of boards:  500

Ball  Winners Cumulative  Prob 1 Board    Prob No   Prob Some
               Winners      Not Won      Board Won  Board Won

 52        1        1       0.999990     0.995012    0.004988
 55        3        4       0.999960     0.980198    0.019802
 56        7       11       0.999890     0.946482    0.053518
 57        8       19       0.999810     0.909365    0.090635
 58       17       36       0.999640     0.835243    0.164757
 59       35       71       0.999290     0.701085    0.298915
 60       63      134       0.998660     0.511479    0.488521
 61       75      209       0.997910     0.351307    0.648693
 62      154      363       0.996370     0.162301    0.837699
 63      228      591       0.994090     0.051624    0.948376
 64      379      970       0.990300     0.007645    0.992355
 65      529     1499       0.985010     0.000525    0.999475
 66      862     2361       0.976390     0.000006    0.999994
 67     1327     3688       0.963120     0.000000    1.000000
 68     2103     5791       0.942090     0.000000    1.000000
 69     3229     9020       0.909800     0.000000    1.000000
 70     4611    13631       0.863690     0.000000    1.000000
 71     6927    20558       0.794420     0.000000    1.000000
 72    10341    30899       0.691010     0.000000    1.000000
 73    15244    46143       0.538570     0.000000    1.000000
 74    22017    68160       0.318400     0.000000    1.000000
 75    31840   100000       0.000000     0.000000    1.000000

Un 1000 tableros solo reduce el punto medio a 59 bolas de 60. El número esperado casi con certeza será entre 58 y 63 para cualquier juego razonable.

Gracias a @Hooked por una respuesta muy útil. Como señala @ross-millikan en un comentario allí, presentar datos CDF ( función de distribución acumulativa ) de las simulaciones es muy útil para extender la respuesta a N jugadores.

Porté ese código a Python 3 e hice algunas modificaciones más (por ejemplo, para extraer el CDF) en https://github.com/nealmcb/bingo-hooked . Con 10 millones de juegos simulados, la función de densidad de probabilidad (PDF) es mucho más fluida:

La media y la desviación estándar son aproximadamente 42,37 y 9,87

La tabla CDF de Bingo de la misma tirada grande también está disponible en ese repositorio, lo que indica que, por ejemplo, hay un 1 % de posibilidades de acertar un BINGO con 18 llamadas y un 10 % con 29.