Bingo Cards and the Empty Supreme Court

The Riddler for April 14, 2017. The Express counts standard $5\times 5$ American bingo cards: each column draws from a disjoint pool of $15$ numbers, with a free centre square. The Classic asks for the expected number of vacancies on a nine-seat Supreme Court when justices’ tenures are uniform on $[0,40]$ years and seats can only be filled when the same party controls the presidency and the Senate.

Riddler Express

A standard American bingo card is a $5 \times 5$ grid. The five columns are labelled B, I, N, G, O. Column B contains five distinct numbers from $\{1,\ldots,15\}$, column I five distinct numbers from $\{16,\ldots,30\}$, and so on through column O drawing from $\{61,\ldots,75\}$. The centre square (column N, row 3) is a “free space” and carries no number. How many distinct bingo cards are there?

The Riddler, FiveThirtyEight, April 14, 2017(original post)

Solution

The columns are independent: the pool for each column is disjoint from the others, so filling one column places no constraint on another. Two cards are different if any cell differs. Within column B, we choose an ordered $5$-tuple of distinct numbers from $\{1,\ldots,15\}$ (order matters because row positions are part of the card’s identity). That count is the falling factorial $$15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \;=\; \frac{15!}{10!} \;=\; 360\,360.$$ The columns I, G and O give the same count. Column N is identical except for the free centre square, so it places only four numbers, with count $$15 \cdot 14 \cdot 13 \cdot 12 \;=\; 32\,760.$$ Multiplying: $$(15 \cdot 14 \cdot 13 \cdot 12 \cdot 11)^4 \cdot (15 \cdot 14 \cdot 13 \cdot 12) \;=\; 360\,360^4 \cdot 32\,760.$$ The exact value is $$\boxed{\,552{,}446{,}474{,}061{,}128{,}648{,}601{,}600{,}000 \;\approx\; 5.52 \times 10^{26}.\,}$$

The computation

Encode the rule directly: factor each column’s count from the disjoint pool, with the centre square skipped in column N, and multiply.

from math import prod

def falling(n, k):
    return prod(range(n - k + 1, n + 1))

cols_BIGO = falling(15, 5)                                  # 15*14*13*12*11
col_N     = falling(15, 4)                                  # 15*14*13*12 (free centre)
total = cols_BIGO**4 * col_N
print(f"B,I,G,O column count = {cols_BIGO}")
print(f"N column count       = {col_N}")
print(f"total bingo cards    = {total}")
print(f"approx               = {total:.3e}")
# B,I,G,O column count = 360360
# N column count       = 32760
# total bingo cards    = 552446474061128648601600000
# approx               = 5.524e+26

Riddler Classic

The Supreme Court has nine seats. At the start of time the bench is empty. Each election, each party has an independent $50\%$ chance of winning the presidency and an independent $50\%$ chance of winning the Senate, so the government is “aligned” (same party in both branches) with probability $1/2$. Elections occur every two years. A vacancy can only be filled in an election cycle when the government is aligned; otherwise the seat waits for the next election. Each appointed justice serves a tenure drawn uniformly from $[0, 40]$ years, independently of everything else. What is the expected number of vacancies on the bench in the long run? Extra credit: an open “coolest extension” prize.

The Riddler, FiveThirtyEight, April 14, 2017(original post)

Solution

Each of the nine seats behaves identically and independently in expectation. By linearity of expectation the long-run vacancy count is $$\mathbb{E}[\text{vacancies}] \;=\; 9 \cdot p_{\text{vac}},$$ where $p_{\text{vac}}$ is the long-run probability that a single seat is vacant.

One-seat picture. A seat alternates between two phases: filled (a justice serves a tenure $T \sim \text{Uniform}(0, 40)$, with $\mathbb{E}[T] = 20$ years) and vacant (waiting for an aligned election). The fraction of time the seat is vacant equals the ratio of expected vacant time to expected cycle time (one filled phase plus one vacant phase): $$p_{\text{vac}} \;=\; \frac{\mathbb{E}[W]}{\mathbb{E}[T] + \mathbb{E}[W]},$$ where $W$ is the wait from the moment of vacancy to the next aligned election.

Computing $\mathbb{E}[W]$ (the simple approximation). At the moment of vacancy, treat the government’s alignment as a fair coin (this is the standard simplification). With probability $1/2$ it is aligned and the seat is filled at the next election cycle; treat that as wait $0$ (the post does so). With probability $1/2$ the government is misaligned, and the seat waits for the next aligned election. Since congressional elections occur every two years and alignment at each election is an independent fair coin, the number of additional elections waited is geometric with mean $2$ (one initial misalignment plus an expected one more election before alignment). Each election is two years apart. Conditioning on the first sub-case (aligned at the moment of vacancy) wait is $0$; conditioning on the second (misaligned), the wait is the time to the next election, on average $1$ year, plus a further geometric tail of expected $2$ years (an extra election with probability $1/2$, geometric mean $2$ years on average). So $$\mathbb{E}[W \mid \text{misaligned}] \;=\; 1 + 2 \;=\; 3 \text{ years},$$ and $$\mathbb{E}[W] \;=\; \tfrac{1}{2}\cdot 0 + \tfrac{1}{2}\cdot 3 \;=\; 1.5 \text{ years}.$$ Hence $$p_{\text{vac}} \;=\; \frac{1.5}{20 + 1.5} \;=\; \frac{3}{43},$$ and $$\mathbb{E}[\text{vacancies}] \;\approx\; 9 \cdot \frac{3}{43} \;=\; \frac{27}{43} \;\approx\; 0.628.$$

The refinement. The assumption that the government is misaligned with probability $1/2$ at the moment of vacancy is not quite right: a justice’s tenure begins in an aligned government, and short tenures end in a still-aligned government (no election having intervened). After accounting for this bias toward alignment at the moment of vacancy, Hector Pefo’s careful integration gives $\mathbb{E}[\text{vacancies}] \approx 0.606$.

The headline answer:

Extra credit

The 2017 post offered a “coolest extension” prize for variations: correlated election outcomes, different tenure distributions, different court sizes. The qualitative finding from solvers (notably Conor Smith’s extension) was that if presidential and Senate outcomes are positively correlated, the expected vacancies drop, settling around $0.45$ when the two are perfectly correlated. The mechanism is direct: stronger correlation raises the chance of alignment at each election from $1/2$ toward $1$, shortening the wait $W$.

The computation

Encode the process itself: simulate over a long horizon. At each event time (next election, or next seat vacancy), advance the state, flip a new alignment if the event is an election, and fill all vacant seats with new tenures if aligned. Record the fraction of time the bench has each number of vacancies.

1. Maintain remaining-tenure timers for each of $9$ seats; a seat is vacant when its timer is $\le 0$.

2. Maintain a clock until the next election ($2$-year cadence) and a current alignment bit.

3. Advance to the next event (election or seat vacancy), accumulating $\text{vacancies} \cdot \Delta t$.

4. At elections, flip alignment; if aligned, fill every vacant seat with a fresh $\text{Uniform}(0,40)$ tenure.

import random

def simulate(T=200_000, burn=20_000, seed=0, N=9):
    rng = random.Random(seed)
    tenures = [0.0] * N                                    # all seats start empty
    aligned = rng.random() < 0.5
    time = 0.0
    total_vac_time = 0.0
    counted_time = 0.0
    while time < T:
        # advance through one 2-year cycle; alignment is constant within it.
        t_end = time + 2.0
        cur = time
        while cur < t_end:
            positives = [t for t in tenures if t > 0]
            step = min(min(positives), t_end - cur) if positives else t_end - cur
            vac_now = sum(1 for t in tenures if t <= 0)
            if cur >= burn:
                total_vac_time += step * vac_now
                counted_time += step
            for i in range(N):
                if tenures[i] > 0:
                    tenures[i] -= step
                    if tenures[i] < 1e-12: tenures[i] = 0.0
            cur += step
            # mid-cycle: if aligned, fill any seat that just became vacant
            if aligned and cur < t_end - 1e-12:
                for i in range(N):
                    if tenures[i] <= 0:
                        tenures[i] = rng.uniform(0, 40)
        # election: new alignment; if aligned now, fill any still-vacant seat
        aligned = rng.random() < 0.5
        if aligned:
            for i in range(N):
                if tenures[i] <= 0:
                    tenures[i] = rng.uniform(0, 40)
        time = t_end
    return total_vac_time / counted_time

print(f"empirical E[vacancies] = {simulate():.3f}")
# empirical E[vacancies] = 0.612

The simulation reports about $0.61$ vacancies, agreeing with Hector Pefo’s refined $0.606$ and within range of the simple analytic estimate ($27/43 \approx 0.628$).