[Math] BINGO Probability: Controlling average game duration

probabilityrecreational-mathematics

I wandered over here from StackOverflow and my understanding of advanced mathematics is limited, so bear with me…

A standard, BINGO game card has 24 numbers arranged in a 5×5 format. The center of the card has a free space. The numbers range from 1 to 75. Each column has 1/5 of the numbers (1-15, 16-30, etc). Every round results in a single number being called. To win, a player must have 5 numbers in a row, column, or diagonal for a total of 12 possible ways to win.

My understanding is that a single player will on average call bingo in 41.36 rounds. See Wizard of Odds.

As the number of players increase, does the average rounds to win decrease?
Would proportionally increasing the number range (e.g. 1-85 instead of 1-75) cancel the effect of the increased number of players? If so, how is it related?

GOAL: Given a fixed set of players P and a desired number of rounds R, how large should the set of numbers N be?

Example: For 100 players, how large should the set of numbers be for the game to last, on average, 50 rounds?

Best Answer

Yes, but it can not be made arbitrarily small. As the number of players increases, the expected number of turns to finish the game will approach $4$.
Yes it would, the average game length can be made arbitrarily long if enough numbers are used for the balls. The exact relationship is probably very complicated.

I've opted for a numerical approach, since the probabilities for BINGO are extremely not obvious. I wrote a Python program which (approximately) answers the question: "How many total numbers do we need to make a game last Nturns given that we have Nplayers people playing?" Note that the number of numbers needs to be a multiple of $5$, otherwise one column would be biased. Since $50$ turns seems to be a good average length for a game, if we just set $R = 50$, I've found an experimental fit for $1\leq P \leq 100$. See this graph:

Experimental fit

Note that to answer your example question, the model gives $N \approx 256.5$, so we probably need $255$ numbers. Here is the program if you want to compute some results more accurately; simply change the arguments of how_many_numbers(Nplayers, Nturns).

from random import shuffle, sample

# General plan: card represented as 5x5 arrays of ints, with
# filled spaces represented by 0's and called numbers being
# represented by [column number, actual number].
# Bingo is obtained with straight lines (including diagonals)

def generate_card(N): # makes fresh card with N numbers (mod 5)
    N_per_col = N/5 # numbers per column
    card = []
    for x in range(0, 5):
        card.append(sample(range(1 + x*N_per_col, N_per_col + 1 + x*N_per_col), 5))
    card[2][2] = 0 # free space
    return card


def generate_draws(N): # makes randomized list of balls to be drawn 
    # for N numbers/card (mod 5)
    N_per_col = N/5
    draws = []
    for x in range(0, 5):
        for y in range(1 + x*N_per_col, N_per_col + 1 + x*N_per_col):
            draws.append([x, y])
    shuffle(draws)
    return draws


def did_i_win(card, filled): # simulates player checking
    # whether or not they won after adding "filled". Player
    # only checks the row an column of the last number he filled,
    # or the diagonal if necessary.
    for column in range(0, 5):
        if card[filled[0]][column] != 0:
            for row in range(0, 5):
                if card[row][filled[1]] != 0:
                    if filled[0] == filled[1] or filled[0] + filled[1] == 4:
                        for x in range(0, 5):
                            if card[x][x] != 0:
                                    for y in range(0, 5):
                                        if card[y][4 - y] != 0:
                                            return 0
                                    return 1
                        return 1
                    else:
                        return 0
            return 1
    return 1


def update_card(mycard, called): # simulates player
    # updating all their cards with the most
    # recently called number; returns 1 if BINGO
    newcard = mycard
    for row in range(0, 5):
        if newcard[called[0]][row] == called[1]:
            newcard[called[0]][row] = 0
            if did_i_win(newcard, [called[0], row]) == 1:
                return 1
    return newcard


def grid_print(card): # Prints a card out as a grid, only used for debugging
    for x in range(0, 5):
        print card[0][x], card[1][x], card[2][x], card[3][x], card[4][x]


def play_game(Nplayers, Nnumbers): # Simulates the players playing a game,
    # returns the number of turns taken for the game to finish
    hands = [] # all players' hands
    for x in range(0, Nplayers):
        hands.append(generate_card(Nnumbers))
    undrawn = generate_draws(Nnumbers) # balls in wheel
    Nturns = 0
    while True: # while no one has won
        Nturns = Nturns + 1
        card = undrawn.pop(0) # Ball drawn and discarded
        for x in range(0, Nplayers): # Players update their hands
            hands[x] = update_card(hands[x], card)
            if hands[x] == 1: # if a player won
                return Nturns


def Exp_N(Ntrials, Nplayers, Nnumbers): # Runs Ntrials simulations and returns 
    # the expected number of turns until a bingo is reached in a game with 
    # Nplayers players and Nnumbers available for the cards
    turns = 0
    for x in range(0, Ntrials):
        turns = turns + play_game(Nplayers, Nnumbers)
    return float(turns)/Ntrials


def how_many_numbers(Nplayers, Nturns): # Determines how many numbers 
    # are needed for a game with Nplayers to last Nturns
    N = 25
    while True:
        Nturns_N = Exp_N(10, Nplayers, N) # change the 10 to 100 for greater accuracy
        if Nturns_N > Nturns:
            best_N = N
            score = abs(Nturns_N - Nturns)
            for N2 in range(N - 25, N + 25 + 1, 5):
                d = abs(Exp_N(100, Nplayers, N2) - Nturns) # change the 100 to 
                # 1000 for greater accuracy
                if d < score:
                    best_N = N2
                    score = d
            return best_N

        N = N + 5

print how_many_numbers(1, 42)

Related Solutions

[Math] Game related to probability

Assuming that "Bingo" means complete row or column or diagonal, I computed the following numbers (count of "winning pattern") by computer: $$S[0] = 0\\ S[1] = 0\\ S[2] = 0\\ S[3] = 0\\ S[4] = 16\\ S[5] = 360\\ S[6] = 3800\\ S[7] = 25080\\ S[8] = 116040\\ S[9] = 399048\\ S[10] = 1053120\\ S[11] = 2167368\\ S[12] = 3493152\\ S[13] = 4380480\\ S[14] = 4197720\\ S[15] = 2975160\\ S[16] = 1478304\\ S[17] = 472392\\ S[18] = 84312\\ S[19] = 6552\\ S[20] = 120\\ S[21] = 0\\ S[22] = 0\\ S[23] = 0\\ S[24] = 0 $$ With these numbers, the probability that the first BINGO is obtained with the $n$th daub equals $$\frac{S[n]}{n\cdot{24\choose n}},$$ provided we can assume that in all situation, the next daub is equally likely to occur among all non-daub positions. This assumption is justified in spite of the not completely random distribution of numbers among columns.

Then the probability that the first BINGO is achieved with $n$ daubs and $m$ draws is $$p(n,m) = S[n]\cdot\frac1{75}\cdot\frac{75-24\choose m-n}{74\choose m-1} $$ For each winning pattern, the last number drawn must be the last daub of the pattern and the remaining $m-n$ numbers not determined by the winning pattern must be taken from the $75-24$ losing numbers, while in principle there are 74 numbers to chose the $m-1$ first draws (i.e. without the last draw). For example, $p(4,5)=\frac{136}{14382825}$.

Note (to quote D.E.Knuth): I have only proved the above calculations correct, not tested them - so there may be errors.

Probability – Expected Number of Calls for Bingo Win

As evidenced by some of my previous answers, I like to write quick numerical simulations if they seem feasible. Bingo seems especially easy (Python code below).

I'm not sure if this is true, but I think the Bingo cards are essentially independent of each other. That is, if we can compute the probability distribution of a single player $N=1$ game length, we can use that to compute the joint probabilities for any number of players.

What I get seems to match with your playing experience, the mean game length for a single player was $42.4$ with a standard deviation of $9.6$. There is a slight skew in the PDF towards longer games. The full PDF is shown below:

enter image description here

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()

Best Answer

Related Solutions

[Math] Game related to probability

Probability – Expected Number of Calls for Bingo Win

Related Question