Monthly Archives: February 2025

Expected time to complete a WOW board row or column

Posted on by
Reply

I recently saw a WOW board, which seems to be a popular approach to rewarding positive behaviors in elementary classrooms. The idea is pretty simple: start with an n \times n grid (usually n=10) of empty squares. When a student exhibits some positive behavior, academic achievement, etc., they write their name or otherwise fill in a randomly chosen square. When the grid is “filled,” something cool happens, such as a prize drawing, extra recess, gold watches for everyone, whatever.

In most descriptions of WOW boards that I found online, the students must fill the entire grid of all 100 squares. But this particular variant was more mathematically interesting: the grid squares were numbered 1 to 100, and the teacher kept a container of slips also numbered 1 to 100; each time a student filled in a square, they didn’t simply pick any open spot on the board, but instead drew one of the slips from the container (without replacement) to determine which square to write their name in. The cool-something happens when the students first complete any row or column of the grid.

How long, on average, does this take? That is, what is the expected value of X, the number of slips drawn until first completing a row or column of the grid?

This is essentially a special case of the game of Bingo discussed here before. However, the analysis approaches presented there required computing sums with an exponential number of terms: 2^{n^2} for the most brute-force approach, which we knocked down to 2^{2n}. This is manageable for Bingo cards with n=5, but is already unpleasant for a WOW board with n=10.

It’s a nice problem to show that we can more efficiently compute the probability distribution– and thus the expected value– of X in polynomial time using the formula

P(X>k)=\frac{1}{{n^2 \choose k}} \sum\limits_{i=0}^n \sum\limits_{j=0}^n (-1)^{i+j} {n \choose i}{n \choose j}{n^2-ni-nj+ij \choose k-ni-nj+ij}

E(X)=\sum\limits_{k=0}^{n(n-1)} P(X>k)

The resulting cumulative distribution for a 10×10 grid is shown below in blue, with the expected number of draws– about 71.6– shown in red.

An open question that I don’t know how to answer: what is the value of

\lim\limits_{n \to \infty} \frac{E(X)}{n^2}

That is, as the WOW board grid size grows large, do we expect to need to fill closer and closer to 100% of the squares before first filling a row or column?

I suspect the answer is yes, but I’m not sure how to prove it.