Analysis of Bingo

Introduction

Suppose that Alice and Bob play a game for a dollar: they roll a single six-sided die repeatedly, until either:

  1. Alice wins if they observe each of the six possible faces at least once, or
  2. Bob wins if they observe any one face six times.

Would you rather be Alice or Bob in this scenario? Or does it matter? You can play a similar game with a deck of playing cards: shuffle the deck, and deal one card at a time from the top of the deck, with Alice winning when all four suits are dealt, and Bob winning when any particular suit is dealt four times. (This version has the advantage of providing a built-in record of the history of deals, in case of argument over who actually wins.) Again, would you rather be Alice or Bob?

It turns out that Alice has a distinct advantage in both games, winning nearly three times more often than Bob in the dice version, and nearly twice as often in the card version. The objective of this post is to describe some interesting mathematics involved in these games, and relate them to the game of Bingo, where a similar phenomenon is described in a recent Math Horizons article (see reference below): the winning Bingo card among multiple players is much more likely to have a horizontal bingo (all numbers in some row) than vertical (all numbers in some column).

Bingo with a single card

First, let’s describe how Bingo works with just one player. A Bingo card is a 5-by-5 grid of numbers, with each column containing 5 numbers randomly selected without replacement from 15 possibilities: the first “B” column is randomly selected from the numbers 1-15, the second “I” column is selected from 16-30, the third column from 31-45, the fourth column from 46-60, and the fifth “O” column from 61-75. An example is shown below.

Example of an American Bingo card.

A “caller” randomly draws, without replacement, from a pool of balls numbered 1 through 75, calling each number in turn as it is drawn, with the player marking the called number if it is present on his or her card. The player wins by marking all 5 squares in any row, column, or diagonal. (One minor wrinkle in this setup is that, in typical American-style Bingo, the center square is “free,” considered to be already marked before any numbers are called.)

It will be useful to generalize this setup with parameters (n,m), where each card is n \times n with each column selected from m possible values, so that standard Bingo corresponds to (n,m)=(5,15).

We can compute the probability distribution of the number of draws required for a single card to win. Bill Butler describes one approach, enumerating the 2^{n^2-1}=2^{24} possible partially-marked cards and computing the probability of at least one bingo for each such marking.

Alternatively, we can use inclusion-exclusion to compute the cumulative distribution directly, by enumerating just the 2^{2n+2}=2^{12} possible combinations of horizontal, vertical, and diagonal bingos (of which there are 5, 5, and 2, respectively) on a card with k marks. In Mathematica:

bingoSets[n_, free_: True, diag_: True] :=
 Module[{card = Partition[Range[n^2], n]},
  If[free, card[[Ceiling[n/2], Ceiling[n/2]]] = 0];
  DeleteCases[Join[
    card, Transpose[card],
    If[diag, {Diagonal[card], Diagonal[Reverse[card]]}, {}]],
   0, Infinity]]

bingoCDF[k_, nm_, bingos_] :=
 Module[{j},
  1 - Total@Map[
      (j = Length[Union @@ #];
        (-1)^Length[#] Binomial[nm - j, k - j]) &,
      Subsets[bingos]]/Binomial[nm, k]]

bingos = bingoSets[5, False, True];
cdf = Table[bingoCDF[k, 75, bingos], {k, 1, 75}];

(Note the optional arguments specifying whether the center square is free, and whether diagonal bingo is allowed. It will be convenient shortly to consider a simplified version of the game, where these two “special” rules are discarded.)

The following figure shows the resulting distribution, with the expected number of 43.546 draws shown in red.

Cumulative probability distribution of a single-card bingo in at most the given number of draws. The average of 43.546 draws is shown in red.

Independence with 2 or more cards

Before getting to the “horizontal is more likely than vertical” phenomenon, it’s worth pointing out another non-intuitive aspect of Bingo. If instead of just a single card, we have a game with multiple players, possibly with thousands of different cards, what is the distribution of number of draws until someone wins?

If P_1(X \leq k) is the cumulative distribution for a single card as computed above, then since each of multiple cards is randomly– and independently– “generated,” intuitively it seems like the probability P_j(X \leq k) of at least one winning bingo among j cards in at most k draws should be given by

P_j(X \leq k) \stackrel{?}{=} 1-(1-P_1(X \leq k))^j

Butler uses exactly this approach. However, this is incorrect; although the values in the squares of multiple cards are independent, the presence or absence of winning bingos are not. Perhaps the best way to see this is to consider a “smaller” simplified version of the game, with (n,m)=(2,2), so that there are only four equally likely possible distinct cards:

The four possible cards in (2,2) Bingo.

Let’s further simplify the game so that only horizontal and vertical bingos are allowed, with no diagonals. Then the game must end after either two or three draws: with a single card, it ends in two draws with probability 2/3. However, with two cards, the probability of a bingo in two draws is 5/6, not 1-(1-2/3)^2=8/9.

Horizontal bingos with many cards

Finally, let’s come back to the initial problem: suppose that there are a large number of players, with so many cards in play that we are effectively guaranteed a winner as soon as either:

  1. At least one number from each of the n=5 column groups is drawn, resulting in a horizontal bingo on some card; or
  2. At least n=5 of m=15 possible numbers is drawn from any one particular column group, resulting in a vertical bingo on some card.

(Let’s ignore the free square and diagonal bingos for now; the former is easily handled but unnecessarily complicates the analysis, while the latter would mean that (1) and (2) are not mutually exclusive.)

Then the interesting observation is that a horizontal bingo (1) is over three times more likely to occur than a vertical bingo (2). Furthermore, this setup– Bingo with a large number of cards– is effectively the same as the card and dice games described in the introduction: Bingo is (n,m)=(5,15), the card game is (4,13), and the dice version is effectively (6,\infty).

The Math Horizons article referenced below describes an approach to calculating these probabilities, which involves enumerating integer partitions. However, this problem is ready-made for generating functions, which takes care of the partition house-keeping for us: let’s define

g_a(x) = \left(\sum_{j=a}^{n-1} {m \choose j}x^j\right)^{n-1}

so that, for example, for Bingo with no free square,

g_1(x) = \left({15 \choose 1}x^1 + {15 \choose 2}x^2 + {15 \choose 3}x^3 + {15 \choose 4}x^4\right)^4

Intuitively, each factor corresponds to a column, where each coefficient of x^j indicates the number of ways to draw exactly j numbers from that column (with some minimum number from each column specified by a). The overall coefficient of x^k indicates the number of ways to draw k numbers in total, with neither a horizontal nor vertical bingo.

Then using the notation from the article, the probability $P(H_k)$ of a horizontal bingo on exactly the k-th draw is

P(H_k) = \frac{mn(k-1)!(mn-k)!}{(mn)!}[x^{k-1}]g_1(x)

and the probability $P(V_k)$ of a vertical bingo on exactly the k-th draw is

P(V_k) = \frac{mn(k-1)!(mn-k)!}{(mn)!} {m-1 \choose n-1} [x^{k-n}](g_0(x)-g_1(x))

The summation

\sum_{k=n}^{(n-1)^2+1} P(H_k)

over all possible numbers of draws yields the overall probability of about 0.752 that a horizontal bingo is observed before a vertical one. Similarly, for the card game with (n,m)=(4,13), the probability that Alice wins is 22543417/34165005, or about 0.66. For the dice game– which requires a slight modification to the above formulation, left as an exercise for the reader– Alice wins with probability about 0.747.

Reference:

  1. Benjamin, A., Kisenwether, J., and Weiss, B., The Bingo Paradox, Math Horizons25(1) September 2017, p. 18-21 [PDF]
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Analysis of Bingo

  1. The dice game answer is so unintuitive to me that, before reading the analogy with Bingo, I just had to run a little Monte Carlo simulation. I was so sure it didn’t matter. I bet you could use this non-intuitive outcome to spot Bingo cheating (a la Benford’s Law), when draws aren’t as random as they’re supposed to be. It’s likely that a repeat cheater wouldn’t have the correct distribution of horizontal and vertical wins.

    • Interesting idea. You’re right, I like this problem because intuition seems to vary a lot. Probably makes for a great bar bet :).

      The dice game is perhaps the best version to “visualize” what’s going on, and to explain the cause of the difference: consider the shortest possible game of just 6 rolls. Of the 6^6 possible outcomes, most of them don’t end in a winner “yet”… but of those that do, Bob is the winner in just 6 outcomes (all 1s, or all 2s, etc.), while Alice is the winner in 6!=720 of them.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s