5x5 board Bingo Question

Question

There is a game which I play, it is like bingo. It starts with a 5x5.

Lets say horizontally it goes ABCDE from left to right and vertically it goes 12345 from bottom to top. I have 2 random generators which will generate a letter and a number giving me a box to cross. So for example A2. Suppose I the generators don't generate a box that has been generated before, what is the probability that after the Nth amount of random generations, I get a bingo horizontally or vertically. I would like to also know the probability of the Nth generation to be a bingo.

Answer 1

Let's say $n$ boxes have been chosen on the 5 by 5 board. There are $N = \binom{25}{n}$ possible arrangements, and we assume all of these are equally likely. Rather than finding the probability of having 5 horizontal or 5 vertical boxes, it seems easier to compute the probability that we do not have 5 horizontal or 5 vertical. We will use the Principle of Inclusion/Exclusion (PIE) to count the number of arrangements which do not have 5 horizontal or 5 vertical boxes marked.

Let's say an arrangement of marks has "property $R_i$" if all the boxes in row $i$ are marked for $1 \le i \le 5$ and has "property $C_j$" if all the boxes in column $j$ are marked, for $1 \le j \le 5$. We want to find $S_i$, the number of arrangements with $i$ of the properties. Notice that if $r$ rows and $c$ columns are completely marked, then those rows and columns contain $5(r+c) - rc$ boxes, leaving $25 - 5(r+c) +rc$ boxes which are not in the rows or columns chosen, of which $n - 5(r+c) +rc$ must be marked. So taking into account the numbers of ways the $r$ rows and $c$ columns can be chosen, $$S_i = \sum_{r+c=i} \binom{5}{r} \binom{5}{c} \binom{25-5(r+c) +rc}{n -5(r+c)+rc}$$ where the sum is taken over all $r$ and $c$ with $r+c=i$, $0 \le r \le 5$ and $0 \le c \le 5$. We can eliminate the $c$ from this expression by using $c = i - r$, with the result $$S_i = \sum_{r=0}^{\min(i,5)} \binom{5}{r} \binom{5}{i-r} \binom{25-5i +r(i-r)}{n -5i+r(i-r)}$$ By PIE, the number of arrangements with none of the properties, i.e. those which do not have any complete columns or rows marked, is $$N_0 = N - S_1 + S_2 - S_3 + \dots + S_{10}$$

The probability that no complete row or column is marked is $N_0 / N$, and the probability that at least one complete row or column is marked is $1-N_0/N$.

By way of a numeric example, by this formula the probability that at least one complete row or column is marked when $n=15$ is 0.487622.

If you would like to know the probability of a bingo on draw $n$, compute the probability that at least one complete row or column is marked by draw $n$ (using the result above) and subtract the probability that at least one complete row or column is marked by draw $n-1$.

Answer 2

Another simple way to evaluate is probability is to use Monte Carlo Simulation,

See my python code:

from random import randint
from functools import reduce

def isBingo(board):
  for i in range(5):
    horizontal = reduce(lambda x,y: x and y, map(lambda j: board[i][j],range(5)), True)
    vertical = reduce(lambda x,y: x and y, map(lambda j: board[j][i],range(5)), True)
    if horizontal or vertical:
      return True
  return False

def monte_carlo(n, iterations=10000):
  count = 0
  for i in range(iterations):
    #Clean board
    board = [[False, False, False, False, False] for j in range(5)]
    for j in range(n):
      #Mark random square
      row = None
      column = None
      while row is None or board[row][column]:
        row = randint(0,4)
        column = randint(0,4)
      board[row][column] = True
    if isBingo(board):
      count += 1.0
  return count/iterations

For example:

print (monte_carlo(15))

0.4876