Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Before I begin, I did a search through math.stackexchange and came across two previous attempts to get people to solve probability problems involving bingo. Neither produced a response.

So what makes me think I'll be any luckier? Maybe some new guy/gal has some insight.

The game of bingo is played with a bingo card having 25 squares, arranged in 5 columns of 5 squares. The first column has numbers between 1-15, the 2nd column has numbers between 16-30, and so on (the 5th column (!) has numbers between 61-75). Someone randomly draws a number from 1-75 and announces it. To make things a little interesting, the middle square is labeled "free". If a number called matches one on your card, you mark it. The goal is to have a complete row, column, or diagonal of 5 marked off first.

Here's my question: what is the expected number of random draws when there is a winner among $N$ players? I was thinking about this because I got involved in such a game this evening with my kids, and it seemed to take an awfully long time for a winner to surface.

My thoughts: this seems to me to be an extremely tough problem. I consider myself better than average in computing expected values, yet I found myself completely stuck on even how to approach the problem. I suppose I could have searched the literature, but I figured I needed to pose a decent question here; I owe it to the users who have posed so many interesting questions here for me to answer.

I'll look for any insight that might move the discussion forward; I do not expect a complete answer for you to post.

share|improve this question
    
@Marvis: Right on your first question, no on the second. The total # of cards is $(15 \cdot 14 \cdot 13 \cdot 12 \cdot 11)^4 (15 \cdot 14 \cdot 13 \cdot 12)$. –  Ron Gordon Jan 18 '13 at 3:17
    
Yes. Thanks. I meant $(15 \times 14 \times 13 \times 12 \times 11)^5/11$. –  user17762 Jan 18 '13 at 3:20
    
Yes. Have you ever played? –  Ron Gordon Jan 18 '13 at 3:21
    
Nope. This is the first time I am even hearing this game. :-) –  user17762 Jan 18 '13 at 3:21
    
I think this is an American thing. Specifically, an American retiree thing (which I am not yet). –  Ron Gordon Jan 18 '13 at 3:23

1 Answer 1

up vote 2 down vote accepted

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()
share|improve this answer
    
For a roomful of $N$ players, it would be more useful to show the cumulative distribution function. Then if there were 100 players, you would expect the winner around the point the CDF hits 0.01, which will be much earlier. My eye says low 20's, but your program will make that easy. –  Ross Millikan Jan 18 '13 at 22:56
    
@Hooked: brilliant work. I may try out your code and see how things behave. Very interesting PDF, I wonder if it is some Poisson shape or something. –  Ron Gordon Jan 19 '13 at 0:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.