binomial - Book Proofs

Round, round, get a round

This week’s Fiddler is about rounding!

Let $\text{round}(x)$ be the value of $x$ rounded to the nearest integer. Suppose $x_1,\dots,x_n$ are independent uniformly distributed random variables in $[0,1]$. Find the probability that
\[
\text{round}(x_1+\cdots+x_n) = \text{round}(x_1)+\cdots+\text{round}(x_n)
\]

My solution:
[Show Solution]

Let’s call the probability we seek $p(n)$. The values of the $x_i$ determine what sums are even possible, so let’s consider some cases based on the possible values of $\text{round}(x_1)+\cdots+\text{round}(x_n)$. Suppose that $k$ of the variables are in in the interval $[\tfrac{1}{2},1]$ and the remaining $n-k$ variables are in $[0,\tfrac{1}{2}]$. The probability of this occurring is $\tfrac{1}{2^n}\binom{n}{k}$. In this case,
\[
\sum_{i=1}^n \text{round}(x_i) = k
\]Note: We can ignore the issue of whether $\tfrac{1}{2}$ rounds to $0$ or $1$ since the probability of $\tfrac{1}{2}$ occurring is zero. Define a set of rescaled variables $y_i$ in $[0,1]$ as follows:
\[
y_i = \begin{cases}
2x_i-1 & \text{if }i=1,\dots,k\\
2x_i & \text{if }i=k+1,\dots,n
\end{cases}
\]Now let’s calculate the probability that the sum of the $x_i$ also rounds to $k$ and express it in terms of the $y_i$:
\begin{align*}
\mathrm{Prob}\left( \text{round}\biggl(\sum_{i=1}^n x_i\biggr) = k\right)
&= \mathrm{Prob}\left( k-\tfrac{1}{2} \leq \sum_{i=1}^n x_i \leq k+\tfrac{1}{2} \right) \\
&= \mathrm{Prob}\left( k-1 \leq \sum_{i=1}^n y_i \leq k+1 \right)
\end{align*}The sum of the $y_i$, which is a sum of $n$ independent variables in $[0,1]$ follows a so-called Irwin-Hall distribution, whose CDF is given by:
\[
F(x) = \text{Prob}\bigl( y_1+\cdots+y_n \leq x \bigr) = \frac{1}{n!}\sum_{k=0}^{\lfloor x \rfloor} (-1)^k \binom{n}{k}(x-k)^n
\]Therefore, the probability we seek is $F(k+1)-F(k-1)$, or:
\[
\frac{1}{n!}\sum_{m=0}^{k+1} (-1)^m \binom{n}{m}(k+1-m)^n
-\frac{1}{n!}\sum_{m=0}^{k-1} (-1)^m \binom{n}{m}(k-1-m)^n
\]Rearranging terms a bit, we obtain:
\[
\frac{(-1)^{n+k}}{n!} \binom{n}{k}+
\frac{1}{n!}\sum_{m=0}^{k} (-1)^m \binom{n}{m}\bigl( (k+1-m)^n-(k-1-m)^n\bigr)
\]By writing out the terms carefully, we can group like $n^\text{th}$ powers and we obtain a simpler equivalent expression:
\[
\frac{1}{n!}\sum_{m=0}^k(-1)^m\left[ \binom{n+1}{m}-\binom{n+1}{m-1}\right](k+1-m)^n
\]Remember this was the probability that the two roundings are the same when $k$ of the $x_i$’s round to $1$. Multiplying each such probability by its prior probability and summing, we get the total probability that the two roundings are the same:
\[
p(n) = \frac{1}{2^n\,n!}\sum_{k=0}^n \binom{n}{k}\sum_{m=0}^k(-1)^m\left[ \binom{n+1}{m}-\binom{n+1}{m-1}\right](k+1-m)^n
\]This can be further simplified by grouping $n^\text{th}$ powers once again and observing that all odd terms cancel out. After quite a bit of algebra, we obtain the simplest expression possible, which is:

$\displaystyle
p(n) = \frac{1}{2^n\, n!}\sum _{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor } (-1)^k \binom{n+1}{k} (n+1-2k)^n
$

We can evaluate this for different values of $n$ and we obtain:
\[
\begin{array}{c|cccccccccc}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \hline
p(n) & 1 & \frac{3}{4} & \frac{2}{3} & \frac{115}{192} & \frac{11}{20} & \frac{5887}{11520} & \frac{151}{315} & \frac{259723}{573440} & \frac{15619}{36288} & \frac{381773117}{928972800}
\end{array}
\]

The sequence $2^n \, n!\, p(n)$ is actually a well-known sequence. It is A261398 in OEIS (the Online Encyclopedia of Integer Sequences), and according to OEIS it has no known closed-form formula and the one above is the simplest one available. Good enough for me!

Visualization in 2D and beyond

We can visualize the probabilities for the case $n=2$ by coloring in the set of points $(x_1,x_2)$ for which the sum of the rounded values equals the rounded value of the sum. This yields:

We can check the shaded region is $\frac{3}{4}$ of the total area, as anticipated. We can do the same for $n=3$. This time, we plot the set of points $(x_1,x_2,x_3)$ and the probability is the shaded volume:

Again, we can check the volume is $\frac{2}{3}$. Unfortunately, we can’t visualize the case $n=4$, but we can try… This should be a 4D hypercube. In the same way that each slice of a 3D cube is a square, each slice of a 4D hypercube is a 3D cube. Here is an animation showing what happens as we vary $x_4 \in [0,1]$ and we plot the cube resulting from the valid choices of $(x_1,x_2,x_3)$ as a function of $x_4$. The abrupt change occurs when $x_4=\tfrac{1}{2}$ as this causes the sum of rounded values to jump by $1$.

So now, if you can imagine, the probability we’re looking for is the “hyper-volume” of this 4D shape, which is given by integrating the volume above as we vary $x_4$, and as it turns out,
\[
p(4) = \int_{0}^1 \text{Volume}(x_4)\,\mathrm{d}x_4 = \frac{115}{192}.
\]

Approximation

Recall that the solution we found above is given by
\[
p(n) = \sum_{k=0}^n \frac{1}{2^n}\binom{n}{k}\bigl( F(k+1)-F(k-1) \bigr)
\]where $F(x)$ is the CDF of the Irwin-Hall distribution. The formula we found for this is quite messy, so let’s see if we can approximate it.

First, the Irwin-Hall distribution can be well-approximated by a normal distribution. This makes sense, since summing a large number of identically distributed random variables tends to a normal distribution by the central limit theorem. In this case, the limiting distribution has mean $\mu=\frac{n}{2}$ and variance $\sigma^2=\frac{n}{12}$. Therefore, we can approximate:
\begin{align*}
F(k+1)-F(k-1) &\approx 2F'(k) \\
&\approx \frac{2}{\sqrt{2\pi \sigma^2}} \exp\biggl( -\frac{(x-\mu)^2}{2\sigma^2} \biggr) \\
&= \frac{1}{\sqrt{\pi n/24}}\exp\biggl( -\frac{(k-\tfrac{n}{2})^2}{n/6} \biggr)
\end{align*}Next, the weighted binomial sum is actually a binomial distribution, which we can also approximate using a normal distribution. In general, we have $B(n,p) \approx \mathcal{N}(\mu,\sigma^2)$, with $\mu=np$ and $\sigma^2=np(1-p)$. Therefore, if $g$ is any function, we can write the binomial sum as an expectation:
\begin{align*}
\sum_{k=0}^n \frac{1}{2^n}\binom{n}{k} g(k)
&= \mathbb{E}_{k \sim B(n,\tfrac{1}{2})}\bigl( g(k) \bigr) \\
&\approx \mathbb{E}_{k \sim \mathcal{N}(\tfrac{n}{2},\tfrac{n}{4})}\bigl( g(k) \bigr) \\
&=\frac{1}{\sqrt{\pi n/2}} \int_{-\infty}^\infty \exp\biggl(-\frac{(k-\tfrac{n}{2})^2}{n/2} \biggr)g(k)\,\mathrm{d}k
\end{align*}Setting $g(k)=F(k+1)-F(k-1)$ and substituting our previous approximation, we find:
\begin{align*}
p(n) &\approx \frac{1}{\sqrt{\pi n/2}}\frac{1}{\sqrt{\pi n/24}}\int_{-\infty}^\infty \exp\biggl( -\frac{(k-\tfrac{n}{2})^2}{n/6} \biggr)\exp\biggl(-\frac{(x-\tfrac{n}{2})^2}{n/2} \biggr)\,\mathrm{d}k \\
&= \frac{\sqrt{48}}{\pi n} \int_{-\infty}^\infty \exp\biggl(-\frac{(k-\tfrac{n}{2})^2}{n/8} \biggr) \,\mathrm{d}k \\
&= \frac{\sqrt{48}}{\pi n} \sqrt{\pi n/8} \\
\end{align*}Therefore, we have:

$\displaystyle
p(n) \approx \sqrt{\frac{6}{\pi n}}
$

To check our approximation, we can plot it together with the true values:

Not bad! So in conclusion, we have an exact formula and an asymptotically exact approximation for the probability that
\[
\text{round}(x_1+\cdots+x_n) = \text{round}(x_1)+\cdots+\text{round}(x_n)
\]They are given by:

$\displaystyle
p(n) = \frac{1}{2^n\, n!}\sum _{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor } (-1)^k \binom{n+1}{k} (n+1-2k)^n
\approx \sqrt{\frac{6}{\pi n}}
$

Tiling a Tilted Square

This week’s Fiddler is a challenging counting problem.

Consider the following array of 25 squares:

You are filling the array with rectangles by repeating the following two steps:

Select one of the 12 squares along the outer perimeter that has not yet been selected as part of a rectangle.
Form the largest rectangle you can that includes the square you just selected and other squares that are not yet part of any such rectangle.

You repeat these steps until every square along the perimeter has been selected. Here are two final states you might encounter:

How many distinct final states are possible? (Note: States that are rotations or reflections of each other should be counted as distinct.)

My solution:
[Show Solution]

We will solve the problem in three steps, where each time we build up from the previous step and add layers of complexity.

Step 1: one quarter

First, consider the original problem, but with one quarter of the shape:

If we ask about tiling this shape using the procedure outlined in the problem statement, then we can write a recursion in the general case. To see why, start by picking one of the edge squares. This divides the shape into two similar but smaller shapes. For example, if there are $n=6$ edge squares and we pick the third one from the top, we obtain:

We are left with the cases $n=2$ and $n=3$, which we can further subdivide. If we call $c_n$ the number of tilings of this shape, we therefore have the recursion:
\[
c_0=1,\quad\text{and}\quad c_{n+1} = \sum_{k=0}^n c_k c_{n-k}\quad\text{for }n\geq 0
\]This is the well-known recurrence relation for the Catalan numbers. The first few Catalan numbers are (starting from $n=0$):
\[
\{c_n\} = \{1, 1, 2, 5, 14, 42, 132, 429, 1430,\dots\}
\]and a general formula is given by:
\[
c_n = \frac{1}{n+1}\binom{2n}{n}
\]

Step 2: one half

Now, consider the original problem, but with one half of the shape:

If we ask about tiling this shape, we can form a recurrence relation like we did in Step 1. This time, when we pick an edge square, we draw one large rectangle and we are left with a half-shape (up top) and identical quarter-shapes (on either side). For example, if there are $n=6$ edge squares and we pick the fourth from the top, we obtain:

If we call $d_n$ the number of tilings of this shape, we therefore have the recursion:
\[
d_0=1,\quad\text{and}\quad
d_{n+1} = \sum_{k=0}^n c_{n-k}^2 d_k\quad\text{for }n\geq 0
\]The first few numbers in this sequence are (starting from $n=0$):
\[
\{d_n\} = \{1, 1, 2, 7, 38, 274, 2350, 22531, 233292,\dots\}
\]

Step 3: the whole thing

Now consider the original problem. You can probably guess the pattern by now… By picking one of the edge squares, we subdivide the problem into four half-shapes in identical pairs (north-south and east-west). If we call $e_n$ the number of tilings of the whole shape, we therefore have the formula:
\[
e_0=1,\qquad\text{and}\quad
e_{n+1} = \sum_{k=0}^n d_{n-k}^2 d_k^2\quad\text{for }n\geq 0
\]The first few numbers in this sequence are (starting from $n=0$):
\[
\{e_n\} = \{1, 1, 2, 9, 106, 3002, 153432, 11209105, 1027079042\}
\]

Unfortunately, none of this is particularly satisfying since we do not have a closed-form solution for $e_n$. Let’s try to find one…

Attempt at a closed-form solution

A good place to start is to see how the closed-form solution for the Catalan numbers is derived. One way is to use generating functions. The idea is that we define an infinite polynomial (a power series) where the coefficients are the sequence we care about. For Catalan numbers, we have:
\[
C(x) = \sum_{n=0}^\infty c_n x^n
\]Now notice that the recurrence relation for Catalan numbers is a convolution, which we can obtain by squaring $C(x)$:
\begin{align*}
C(x)^2 &= \sum_{m=0}^\infty \sum_{k=0}^\infty c_m c_k x^{m+k} \\
&= \sum_{n=0}^\infty \left(\sum_{k=0}^n c_k c_{n-k} \right)x^n \\
&= \sum_{n=0}^\infty c_{n+1} x^n \\
&= \frac{1}{x}\left( C(x)-1\right)
\end{align*}Solving for $C(x)$, we obtain:
\[
C(x) = \frac{1-\sqrt{1-4x}}{2x}
\](The other root of the quadratic can be excluded since it does not satisfy $C(0)=c_0=1$) From here, we can perform a series expansion via the binomial theorem and extract the coefficient of $x^n$, which yields the formula $c_n = \frac{1}{n+1}\binom{2n}{n}$.

We can use a similar argument to obtain a generating function for $d_n$. To this effect, define:
\[
D(x) = \sum_{n=0}^\infty d_n x^n
\]Now, we can write:
\begin{align*}
D(x) &= 1 + \sum_{n=0}^\infty d_{n+1} x^{n+1} \\
&= 1 + \sum_{n=0}^\infty \sum_{k=0}^n c_{n-k}^2 d_k x^{n+1} \\
&= 1 + \sum_{k=0}^\infty \sum_{n=k}^\infty c_{n-k}^2 d_k x^{n+1} \\
&= 1 + \sum_{k=0}^\infty \sum_{n=0}^\infty c_{n}^2 d_k x^{n+k+1} \\
&= 1 + \sum_{k=0}^\infty d_k x^k \sum_{n=0}^\infty c_n^2 x^{n+1} \\
&= 1 + D(x)\sum_{n=0}^\infty c_n^2 x^{n+1}
\end{align*}Therefore, we can express the generating function for $d_n$ in terms of the generating function of squared Catalan numbers:
\[
\hat C(x) := \sum_{n=0}^\infty c_n^2 x^{n+1}\qquad\text{and}\qquad
D(x) = \frac{1}{1-\hat C(x)}
\]According to Mathematica, the series involving squared Catalan numbers can be evaluated in terms of a hypergeometric function. Namely:
\[
\hat C(x) =
\frac{1}{4} \bigl(\, _2F_1(-\tfrac{1}{2},-\tfrac{1}{2};1;16 x)-1\bigr)
\]Unfortunately, this isn’t particularly helpful as there does not appear to be any way to obtain a formula for the coefficient of $x^n$ in the series for $D(x)$.

Continuing in this fashion, we can also define $E(x)$ as the generating function for $e_n$, which we can express in terms of the square of the generating function for $d_n^2$. Namely:
\[
E(x) = \sum_{n=0}^\infty e_n x^n,\qquad
\hat D(x) = \sum_{n=0}^\infty d_n^2 x^{n+1},\qquad
E(x) = 1 + \tfrac{1}{x}\hat D(x)^2
\]But again, this doesn’t really seem helpful as we can’t evaluate $D(x)$ or much less $\hat D(x)$.

If anybody else can make progress on this problem I would love to hear your approach!

Asymptotics

It was pointed out by commenter MarkS that $c_n^2/d_n$ and $c_n^4/e_n$ appear to tend to finite limits as $n\to\infty$. Here is what we get when we plot these quantities up to $n=2000$:

Is there a way we can find the exact values of these limits? Maybe! We’ll make use of the following fact. If the sequences $a_n$ and $b_n$ have corresponding generating functions $A(x)$ and $B(x)$, and these have radius of convergence $R$, then we can write:
\[
\lim_{n\to\infty}\frac{a_n}{b_n} = \lim_{x\to R^-} \frac{A(x)}{B(x)}
\]This works so long as $A(x)$ and $B(x)$ go to $\infty$ as $x\to R^-$, because any finite truncation of the series will be dominated by its last term (largest power of $x$), so the ratio of truncated series just behaves like the ratio of its last terms, which is what we care about (apologies for the hand-waving; hopefully this makes sense!).

Applying this idea, we would like to write:
\[
\lim_{n\to\infty}\frac{c_n^2}{d_n} = \lim_{x\to R^-}\frac{\hat C(x)}{x D(x)} = \lim_{x\to R^-} x \hat C(x)\bigl(1-\hat C(x)\bigr)
\]But there is just one problem… We already established that
\[
\hat C(x) = \sum_{n=0}^\infty c_n^2 x^{n+1} =
\frac{1}{4} \bigl(\, _2F_1(-\tfrac{1}{2},-\tfrac{1}{2};1;16 x)-1\bigr)
\]and as it turns out, the series for this function has a radius of convergence of $R=\frac{1}{16}$. If you’re curious as to why, remember that this is a series where the coefficients are squared Catalan numbers. Catalan numbers have a well-known property that
\[
c_n \sim \frac{4^n}{n^{3/2}\pi},\qquad\text{i.e.,}\quad
\lim_{n\to\infty}\frac{c_n}{\left(\frac{4^n}{n^{3/2}\pi}\right)} = 1
\]Therefore, $c_n^2 \sim 16^n/n^3\pi$, so a necessary condition for $\hat C(x)$ to converge is that $|x|\leq \frac{1}{16}$ (the general term of the series must tend to zero).

So what’s the problem? Here is a 3D plot of $\hat C(z)$ for complex $z$ (vertical axis is magnitude, color-coded by argument) and plotted for $|z|\leq \frac{1}{16}$.

As we can see, nothing is going to infinity near the boundary. How is it possible? It turns out the radius of convergence is $\frac{1}{16}$ because there is a different kind of discontinuity at this point; the argument (rather than the magnitude) becomes discontinuous. You can see it more clearly when the plot is zoomed out to $|z|\leq 1$ (notice the color discontinuity along the positive real axis).

So how do we deal with this problem? We need to transform the series so that it goes to infinity as $x\to\frac{1}{16}$. One way to do this is to take derivatives. This will yield a series with terms like $n a_n x^{n-1}$ and $n b_n x^{n-1}$, and the ratio remains unchanged! Here is a plot of the first derivative, $\hat C'(z)$:

This is better, as now the function appears non-differentiable near $z=\frac{1}{16}$, but it still doesn’t go to infinity. Let’s differentiate again! Here is a plot of $\hat C'{}'(z)$:

Now we’re in business. So the limit we’re looking for is:
\[
\lim_{n\to\infty}\frac{c_n^2}{d_n}
= \lim_{x\to\frac{1}{16}} \frac{\frac{d^2}{dx^2}\Bigl(\frac{1}{x}\hat C(x)\Bigr)}{\frac{d^2}{dx^2}\Bigl(\frac{1}{1-\hat C(x)}\Bigr)}=\left(5-\frac{4}{\pi}\right)^2\approx 13.88874349
\]I used Mathematica in the last step, which can analytically differentiate and evaluate hypergeometric functions. In conclusion, we have the asymptotic formula:

$\displaystyle
d_n \sim \frac{c_n^2}{\left( 5-\tfrac{4}{\pi}\right)^2}
\sim \frac{16^n}{\pi\left( 5-\tfrac{4}{\pi}\right)^2 n^3}
$

Now as for $e_n$, I’m stuck again. In principle we could use the same technique, which would require evaluating:
\[
\lim_{n\to\infty}\frac{c_n^4}{e_n}
= \lim_{x\to R^-} \frac{\frac{d^k}{dx^k}\sum_{n=0}^\infty c_n^4 x^n}{\frac{d^k}{dx^k}E(x)}
= \lim_{x\to R^-} \frac{\frac{d^k}{dx^k}\sum_{n=0}^\infty c_n^4 x^n}{\frac{d^k}{dx^k}\left(1+\frac{1}{x}\hat D(x)^2\right)}
\]where we differentiate however many times necessary to ensure the series diverges as $x\to R^-$. Mathematica is able to evaluate the numerator (it’s hypergeometric functions again, but a different kind this time), so I was able to determine that $R = \frac{1}{256}$ and the smallest $k$ we can use is $5$ (yikes!). But the sticking point is the denominator. Although we found an asymptotic expansion for $d_n$, we don’t have an actual formula. Without this, we can’t evaluate the general term of $\hat D(x)^2$, which depends on all the $d_n$.

Again, if anybody has ideas, let me know in the comments!

Picking a speaker at random

This week’s Fiddler is about selecting a speaker of the house at random. How long will it take?

There are three candidates who want the job of Speaker. All 221 members of the party vote by picking randomly from among the candidates. If one candidate earns the majority of the votes, they become the next Speaker. Otherwise, the candidate with the fewest votes is eliminated and the process is repeated with one less candidate. If two or more candidates receive the same smallest number of votes, then exactly one of them is eliminated at random. What is the average number of rounds needed to select a new Speaker?

Extra Credit
What if there were 10 candidates running for Speaker?

My solution:
[Show Solution]

We will consider a more general case; suppose there are $n$ candidates and $2m+1$ voting members in the party. We write $2m+1$ since there should be an odd number of party members to break ties. Define the following probability:
\[
p(n,m) = \left\{
\begin{array}{l}
\text{Probability that one of the $n$ candidates} \\
\text{wins a majority of the $2m+1$ votes.}
\end{array}
\right\}
\]Let’s find a formula for $p(n,m)$. For a particular candidate to win $k$ votes, $k$ members must vote for the candidate and the remaining members must vote for one of the other $n-1$ candidates. This occurs with probability $\binom{2m+1}{k}\left(\frac{1}{n}\right)^k \left(1-\frac{1}{n}\right)^{2m+1-k}$. The candidate wins a majority if they garner at least $m+1$ of the $2m+1$ votes. We multiply the final result by $n$ since we are counting the probability that any of the $n$ candidates wins a majority. Therefore,
\[
p(n,m) = n\sum_{k=m+1}^{2m+1} \binom{2m+1}{k}\left(\frac{1}{n}\right)^k \left(1-\frac{1}{n}\right)^{2m+1-k}
\]Note: We can add the probabilities of the different candidates winning as we did because the events are disjoint; it is impossible for two candidates to simultaneously win a majority of the votes. If the criteria allowed for overlap, e.g., one candidate winning at least 40% of the vote, then two candidates could win simultaneously, and we would have to account for this case to avoid double-counting.

Making the change of variables $k \mapsto 2m+1-k$, we obtain

$\displaystyle
p(n,m) = n \sum_{k=0}^m \binom{2m+1}{k} \left(1-\frac{1}{n}\right)^{k}\left(\frac{1}{n}\right)^{2m+1-k}
$

We recognize this as $n$ times the CDF of a binomial distribution with $2m+1$ trials and probability $1-\frac{1}{n}$.

What we’re really after is the expected number of rounds required for a candidate to secure a majority of the vote.
\[
f(n,m) = \left\{
\begin{array}{l}
\text{Expected number of rounds until one of the } \\
\text{that one of the $n$ candidates is elected.}
\end{array}
\right\}
\]This will happen in one round with probability $p(n,m)$. It will happen in $k$ rounds if it does not happen in the first $k-1$ rounds, and happens in the $k^\text{th}$ round. Putting this together, we get:

$\displaystyle
f(n,m) = \sum_{k=1}^{n-1} k\cdot p(n-k+1,m) \prod_{i=0}^{k-1} \bigl( 1-p(n-k+1+i,m) \bigr)
$

Unfortunately, these formulas do not simplify in any meaningful way, so we must evaluate them numerically. The first question asks us to compute $f(3,110)$ and the extra credit asks for $f(10,110)$. Calculating these, we obtain:
\begin{align}
f(3,110) &\approx 1.9999995110943353682 \\
f(10,110) &\approx 8.9999995110943296464
\end{align}These are rational numbers, of course, but $f(3,110)$ and $f(10,110)$ have 105-digit and 1357-digit denominators, respectively, when expressed as irreducible fractions, so I will not write them out here! One thing for sure is that it is very unlikely that the voting will end early. It is a virtual certainty that it will go the full $n-1$ rounds until there are only two candidates remaining.

Bonus: Changing the number of voters

The reason it is so difficult to elect a Speaker early is that there are so many voting members, and therefore it is unlikely that one candidate will obtain a majority of the votes by random chance. We can see how this probability would scale if we changed the number of voting members. Here is a plot of $f(n,m)$ for different values of $n$ (number of candidates), as a function of $2m+1$ (number of voting members). In all cases, we see that the expected number of rounds rapidly approaches $n-1$.

The slow car chase

This week’s Fiddler is a problem about probability and a slow car chase!

You and your pursuer are stopped at traffic lights one block away from each other, as shown below. For both cars, it takes 1 minute to get to each subsequent light, and there is a 50-50 chance any light will be red upon arrival (independent of what happened previously). If a light is red, you must wait one minute before it turns green. What is the probability you will make it to the city limits without being caught by your pursuer?

Extra Credit
In the same scenario as before, imagine there are infinitely many lights. On average, how many minutes will it be until you are ultimately caught?

My solution:
[Show Solution]

Can we escape before getting caught?

Let $P(n)$ be the probability that our pursuer will catch us at the $n^\text{th}$ light. To compute this probability, consider the gap between both cars. Initially, this gap is 1, and every time we reach a new light, depending on whether we got a red light and had to wait, or whether our pursuer got a red light and had to wait, the gap can change. Specifically,

The gap does not change if we both get red lights or both get green lights, which occurs with probability $\frac{1}{4}+\frac{1}{4} = \frac{1}{2}$.
The gap decreases by one if we get a red light and our pursuer gets a green light, which occurs with probability $\tfrac{1}{4}$.
The gap increases by one if we get a green light and our pursuer gets a red light, which occurs with probability $\tfrac{1}{4}$.

Initially, both cars have green lights, and since we get caught on the $n^\text{th}$ light, our final light must be red and our pursuer’s final light must be green. This leaves $n-2$ intermediate lights, at which the distance can either increase, decrease, or stay the same. If the distance could only increase or decrease, the total number of ways would be given by $C_{(n-2)/2}$, where $C_n$ is the $n^\text{th}$ Catalan number (see the interpretation of Catalan numbers as “counting mountain ranges”).

In our case, the gap can also stay constant, which complicates matters slightly. If we assume there are $k$ “ups” and $k$ “downs”, this leaves $n-2-2k$ “flats”. It follows that the total number of mountain ranges that may include plateaus is given by:
\[
\sum_{k=0}^{\left\lfloor \tfrac{n-2}{2} \right\rfloor} C_k \binom{n-2}{2k}
\]Each such path has a probability of occurring that depends on the number of flats, namely, it is
\[
\left(\frac{1}{4}\right)^{2k+1} \left(\frac{1}{2}\right)^{n-2-2k}
\]The reason for the $2k+1$ in the first term is that we must account for the “down” at the very end of the path. Putting everything together and substituting the formula for the Catalan number in, we obtain:
\[
P(n) = \sum_{k=0}^{\left\lfloor \tfrac{n-2}{2} \right\rfloor}
\frac{1}{k+1}\binom{2k}{k} \binom{n-2}{2k} \left(\frac{1}{4}\right)^{2k+1} \left(\frac{1}{2}\right)^{n-2-2k}
\]Amazingly, this sum has a closed-form formula, which I found using Mathematica. The probability that our pursuer will catch at the $n^\text{th}$ light is given by:

$\displaystyle
P(n) = \begin{cases}
\displaystyle\frac{1}{4^n\bigl(n-\tfrac{1}{2}\bigr)} \binom{2n}{n} & \text{for }n=2,3,4,\dots \\[1mm]
0 & \text{otherwise}
\end{cases}
$

We can double check that this is a legitimate probability distribution by verifying that $\sum_{n=2}^\infty P(n) = 1$. In other words, we will eventually be caught, it’s just a matter of when. I used Mathematica to evaluate the infinite sum, and it is indeed equal to one!

If we have $n$ lights to go before we reach the city limit, the probability we will escape before getting caught is $1-\sum_{k=2}^n P(k)$, or in other words:
\[
\text{Prob}(\text{escape}) = 1-\sum_{k=2}^n \frac{1}{4^k\bigl(k-\tfrac{1}{2}\bigr)} \binom{2k}{k}
\]Amazingly, this also has a closed-form expression… and thanks again to Mathematica, it is given by:

$\displaystyle
\text{Prob}(\text{escape}) = \begin{cases}
\displaystyle\frac{2}{4^n} \binom{2n}{n} & \text{for }n=2,3,4,\dots \\[1mm]
0 & \text{otherwise}
\end{cases}
$

This is an embarrassingly simple-looking expression, so there is likely a more elegant solution waiting to be found. The solution includes a denominator $4^n$ which is the total number of ways of assigning $\{\text{red},\text{green}\}$ to each of the $2n$ lights. The numerator is $2\binom{2n}{n}$, which must be the number of light assignments that do not lead to capture. If you can figure this out, please let me know in the comments!

In the original problem, we had 5 lights ahead of us, so substituting $n=5$, we obtain a probability of escape of $\frac{63}{128}$, or approximately 49.2%.

We can also check whether our formula holds up numerically. In the plot below, I compare the empirical probability from running 1,000,000 Monte Carlo simulations, and the analytic formula produced above, and we observe that we have a perfect match.

Note: This problem is somewhat similar to an old Riddler problem from 2017 about a horse race. You can check out my write-up for that problem if you’re interested!

Extra credit: time until caught

It takes at least one minute per light to visit all the lights (possibly more, depending on how many times we stop for red lights). Therefore, whenever we are eventually caught, the number of minutes that elapsed must be at least as much as the number of lights we saw.

We are asked to calculate the expected time elapsed until capture. Based on the argument above, we must have:
\[
\mathbb{E}(\text{lights seen until capture}) \leq
\mathbb{E}(\text{time until capture})
\]Let’s calculate the left-hand side. We already calculated $P(n)$, which is the the probability that we will be captured after seeing exactly $n$ lights. Therefore, the left-hand side is equal to $\sum_{n=2}^\infty n P(n)$. It turns out that this sum does not converge!. To see why, we can use the following asymptotic formula (source), which holds as $n\to\infty$.
\[
\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}
\]This leads us to the approximation
\[
P(n) \sim \frac{1}{\bigl(n-\tfrac{1}{2}\bigr)\sqrt{\pi n}}
\]And now we see why there is no convergence… The function $n P(n)$ decays like $\frac{1}{\sqrt{n}}$, and therefore is not summable (it is a $p$-series with $p=\tfrac{1}{2}$). Since the expected number of lights is unbounded, then the time until capture must also be unbounded.

But does this make any sense? A probability distribution that has no average? Yes! In general, distributions for which some of the moments are unbounded are called heavy-tailed distributions, and there are many well-known examples. In particular, examples of distributions with unbounded first moments (average does not exist) include the Cauchy distribution, the Pareto distribution, and $P(n)$ defined above.

Betting on football with future knowledge

This week’s Fiddler is a football-themed puzzle with a twist: you can see the future! Sort of.

You know ahead of time that your football team will win 8 of their 12 remaining games, but you don’t know which ones. You can place bets on every game, placing bets either for or against your team. You can bet any amount up to how much you currently have. You want to implement a betting strategy that guarantees you’ll have as much money as possible after the 12 games are complete. If you did so, then after the 12 games how much money would you be guaranteed to have if you started with $100?

My solution:
[Show Solution]

Define our quantity of interest:
\[
a_{n,m} = \left\{\begin{array}{l}
\text{Maximum guaranteed winnings assuming there}\\
\text{are $n$ games remaining, we know our team}\\
\text{will win exactly $m$ of them, and we start with \$1.}
\end{array}\right\}
\]Also let $k_{n,m}$ be the fraction of our money we should bet that achieves the maximum guaranteed winnings. We use negative bets to indicate that we are betting for the other team to win. To illustrate, if we currently have $x$ dollars, we can bet any fraction $-1 \leq k \leq 1$, and the possible cases are:

If our team wins, we gain $k x$, so we now have $(1+k)x$.
If our team loses, we lose $k x$, so we now have $(1-k)x$.

Due to the homogeneous nature of the problem, if we were to start with $x$ dollars instead, then our winnings would just be $x \cdot a_{n,m}$.

Let’s start by looking at some edge cases.

If $m=0$ and $n=0$, we have the trivial case where the season is over, so we can say $a_{0,0} = 1$. In other words, we keep all our money.
If $m=n$, we know with certainty that our team will win all its remaining games. Therefore, we can safely bet all our money on them: $k_{n,n} = 1$ and $a_{n,n} = 2a_{n-1,n-1}$ (we will double our money).
If $m=0$, we know with certainty that our team will lose all its remaining games. Therefore, we can safely bet all our money against them: $k_{n,0}=-1$ and $a_{n,0} = 2a_{n-1,0}$.

In the general case, $0\lt m \lt n$, and we must think a bit more carefully. If we bet $k_{n,m}$, the two possible outcomes are:

If our team wins, we now have $a_{n,m} = (1+k_{n,m})a_{n-1,m-1}$. This is because after a win, there are only $m-1$ wins remaining.
If our team loses, we now have $a_{n,m} = (1-k_{n,m})a_{n-1,m}$. This is because after a loss, we must still win $m$ more times.

We should pick $k_{n,m}$ to maximize the minimum winnings of both possible outcomes, because we are looking at the worst-case. In other words, we want:
\[
a_{n,m} = \max_k\, \min\bigl\{ (1+k)a_{n-1,m-1}, (1-k)a_{n-1,m} \bigr\}
\]As functions of $k$, these are two linear functions; one with positive slope and one with negative slope. The optimal $k$ occurs when the lines cross, that is, when $(1+k)a_{n-1,m-1}=(1-k)a_{n-1,m}$. Solving this equation, we obtain:
\begin{align}
k_{n,m} &= \frac{a_{n-1,m}-a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}, &
a_{n,m} &= \frac{2a_{n-1,m}\cdot a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}
\end{align}Combining our recursion for $a_{n,m}$ with the edge cases derived earlier:
\begin{align}
a_{0,0}&=1 \\
a_{n,0}&=2a_{n-1,0} && \text{for }n=1,2,\dots \\
a_{n,n}&=2a_{n-1,n-1} && \text{for }n=1,2,\dots \\
a_{n,m} &= \frac{2a_{n-1,m}\cdot a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}} &&\text{for }0\lt m \lt n
\end{align}There is a neat trick we can use to solve this recursion. Express everything in terms of the inverse of the minimum winnings. The equations then become linear!
\begin{align}
a_{0,0}^{-1}&=1 \\
a_{n,0}^{-1}&=\frac{1}{2} a_{n-1,0}^{-1} && \text{for }n=1,2,\dots \\
a_{n,n}^{-1}&=\frac{1}{2} a_{n-1,n-1}^{-1} && \text{for }n=1,2,\dots \\
a_{n,m}^{-1}&=\frac{1}{2}\left( a_{n-1,m}^{-1} + a_{n-1,m-1}^{-1} \right) &&\text{for }0\lt m \lt n
\end{align}Solving for the first few terms and arranging them in a pyramid where each row is a different value of $n$, we obtain:
\begin{gather}
a_{0,0}^{-1}=\frac{1}{2^0}\\[2mm]
a_{1,0}^{-1}=\frac{1}{2^1} \qquad a_{1,1}^{-1}=\frac{1}{2^1} \\[2mm]
a_{2,0}^{-1}=\frac{1}{2^2} \qquad a_{2,1}^{-1}=\frac{2}{2^2} \qquad a_{2,2}^{-1}=\frac{1}{2^2} \\[2mm]
a_{3,0}^{-1}=\frac{1}{2^3} \qquad a_{3,1}^{-1}=\frac{3}{2^3} \qquad a_{3,2}^{-1}=\frac{3}{2^3} \qquad a_{3,3}^{-1}=\frac{1}{2^3}\\[2mm]
a_{4,0}^{-1}=\frac{1}{2^4} \qquad a_{4,1}^{-1}=\frac{4}{2^4} \qquad a_{4,2}^{-1}=\frac{6}{2^4} \qquad a_{4,3}^{-1}=\frac{4}{2^4} \qquad a_{4,4}^{-1}=\frac{1}{2^4}
\end{gather}The denominators in each row are increasing powers of two, and the numerators are the sums of the two numerators above! In other words, it’s a scaled Pascal’s triangle! This leads us to the formula:
\[
a_{n,m}^{-1} = \frac{1}{2^{n}} \binom{n}{m},\quad\text{or:}\quad
a_{n,m} = \frac{2^{n}}{\binom{n}{m}}
\]What should our optimal policy be? We can use the formula for $k_{n,m}$ derived earlier and substitute the formula we just found for $a_{n,m}$:
\begin{align}
k_{n,m} &= \frac{a_{n-1,m}-a_{n-1,m-1}}{a_{n-1,m}+a_{n-1,m-1}}
= \frac{2m}{n}-1
\end{align}

Therefore, we have the following minimax-optimal strategy:

$\displaystyle
\begin{array}{l}
\text{If there are $n$ games left to play and our team will} \\
\text{win exactly $m$ of the remaining games, we should}\\
\text{bet a fraction $\frac{2m}{n}-1$ of our money, and we will}\\
\text{multiply our money by at least $\frac{2^n}{\binom{n}{m}}$ by the end.}
\end{array}
$

We can check the edge cases: If $m=0$, we should bet $k_{n,0}=-1$ (bet it all against our team), and we will win $2^n$ (double our money for every remaining game). Similarly, if $m=n$, we should bet $k_{n,n}=1$ (bet it all for our team), and we will again win $2^n$.

To address the original question, if there are $n=12$ games remaining and we will win exactly $m=8$ of them, then starting with $\$100$ and using the optimal betting strategy, we are guaranteed to finish the season with at least $100 \cdot 2^{12} / \binom{12}{8} =\frac{100\cdot 4096}{495} \approx \$827.48$.

We can say something even stronger. This optimal betting strategy will always win exactly $\$827.48$! To understand why, we need to dig a little deeper…

Deeper down the rabbit hole

When using the “optimal” strategy derived earlier, something curious happens. Not only are we guaranteed to win at least $2^n/\binom{n}{m}$ by the end of the season, we are guaranteed to win exactly this much! No matter how the wins and losses are arranged, we will always win the same amount after all games have been played!

We will prove this surprising result in two parts. First, we will show that every arrangement wins the same amount under the optimal betting strategy. Second, we will show that this amount is equal to $2^n/\binom{n}{m}$, the same as the previously derived “lower bound”.

To prove all arrangements win the same amount, imagine two arrangements of wins and losses that only differ by swapping one adjacent win-loss pair. For example, if $n=12$ and $m=8$, we could have:
\begin{gather}
\begin{bmatrix}
W & L & W & \textcolor{blue}{W} & \textcolor{red}{L} & W & L & W & W & W & L & W
\end{bmatrix}\\[2mm]
\begin{bmatrix}
W & L & W & \textcolor{red}{L} & \textcolor{blue}{W} & W & L & W & W & W & L & W
\end{bmatrix}
\end{gather}Suppose that right before the swap occurs, we have $x$ dollars, and there are $n_0$ games remaining, and $m_0$ wins remaining.

In the first case, we bet $\frac{2m_0}{n_0}-1$ and we win. There are now $n_0-1$ games remaining and $m_0-1$ wins remaining. We bet $\frac{2(m_0-1)}{n_0-1}-1$, but this time we lose. So our net winnings after the win and loss are:
\[
\small
\left( 1-\left(\frac{2(m_0-1)}{n_0-1}-1\right)\right)\left(1+\left(\frac{2m_0}{n_0}-1\right)\right)x
=\frac{4m_0 (n_0-m_0)}{n_0(n_0-1)}x
\]
In the second case, we bet $\frac{2m_0}{n_0}-1$ and we lose. There are now $n_0-1$ games remaining and $m_0$ wins remaining. We bet $\frac{2m_0}{n_0-1}-1$, and this time we win. So our net winnings after the loss and win are:
\[
\small
\left( 1+\left(\frac{2m_0}{n_0-1}-1\right)\right)\left(1-\left(\frac{2m_0}{n_0}-1\right)\right)x
=\frac{4m_0 (n_0-m_0)}{n_0(n_0-1)}x
\]

Since swapping an adjacent win-loss pair does not change how much we win, and we can get from any arrangement of $m$ wins and $n-m$ losses to any other arrangement via a suitable sequence of adjacent win-loss swaps, this shows that every arrangement obtains the exact same result!

In particular, we might as well assume we win our first $m$ games, and lose the rest. Let’s calculate how much we win in this simple scenario.

For the first $m$ games, we win every time, so our winnings are:
\[
\frac{2m}{n} \cdot \frac{2(m-1)}{(n-1)} \cdot \frac{2(m-2)}{(n-2)} \cdots \frac{2(1)}{(n-m+1)}
=\frac{2^m m!(n-m)!}{n!}
\]
For the remaining $n-m$ games, we are in an edge case. Our team will lose all remaining games, so we bet against them every time and double our money. This multiplies our money by $2^{n-m}$.

Therefore, our total winnings are:
\[
\frac{2^m m!(n-m)!}{n!} \cdot 2^{n-m} = \frac{2^n}{\binom{n}{m}}
\]This is the same result as the lower bound we found in the first part of the solution! Therefore, we can conclude that using the optimal betting strategy yields exactly the same outcome no matter how the wins and losses are ordered, and this amount is $2^n/\binom{n}{m}$.

A more elegant alternative solution, due in large part to a clever observation by Vince Vatter.
[Show Solution]

The key observation is that we can think of betting strategies as bets on outcomes rather than bets on individual games. For example, if $n=2$, there are four possible outcomes (ignore for now the fact that we have future knowledge about the win-loss record):
\[
LL,LW,WL,WW
\]If I bet all my money on $LW$ and I’m right, then I will double my money twice. If I’m wrong, then I lose everything.

In general, if there are $n$ games, there will be $2^n$ possible outcomes. I don’t have to bet everything on one outcome; I can distribute my $x$ dollars however I like. But only one of these outcomes will come true. The money I bet on that outcome will get multiplied by $2^n$ and all my other bets will be lost.

In the worst case, the outcome with the smallest bet will come true. So if we want a strategy that maximizes the worst-case losses, I should bet an equal amount on each possible outcome.

Now we can use our advance knowledge that our team will win exactly $m$ of the $n$ games. Therefore, only $\binom{n}{m}$ of the $2^n$ outcomes are possible. So the optimal strategy is to distribute our bets equally among all $\binom{n}{m}$ possible outcomes. With this strategy, no matter which outcome comes true, we will always multiply our initial dollar amount by exactly $2^n/\binom{n}{m}$.

I skipped some details here; I didn’t explain why every strategy can be decomposed as a combination of pure strategies, but this post is already quite long so I won’t write out the details. As a partial explanation, the result uses the fact that the earnings are a linear function of the bets. For example, if $n=1$, our strategy consists of the single bet $k$, and the outcome is:
\[
(k) : \begin{cases}
(1+k)x & \text{if W} \\
(1-k)x & \text{if L}
\end{cases}
\]There are also two pure strategies:
\[
(1) : \begin{cases}
0 & \text{if W} \\
2x & \text{if L}
\end{cases}
\qquad\text{and}\qquad
(-1): \begin{cases}
2x & \text{if W} \\
0 & \text{if L}
\end{cases}
\]We can decompose $k$ as a combination of $+1$ and $-1$, which yields:
\[
(k) = \left(\frac{1-k}{2}\right)(1) + \left(\frac{1-k}{2}\right)(-1)
\]In other words, using the bet $k$ is the same as betting $\left(\frac{1-k}{2}\right)x$ of our money on a loss and betting the remaining $\left(\frac{1+k}{2}\right)x$ on a win. Exactly one of those two outcomes will come true, so the amount we bet correctly gets doubled and the amount we bet incorrectly is lost.

Loteria

This week’s Riddler Classic is about Lotería, also known as Mexican bingo!

A thousand people are playing Lotería, also known as Mexican bingo. The game consists of a deck of 54 cards, each with a unique picture. Each player has a board with 16 of the 54 pictures, arranged in a 4-by-4 grid. The boards are randomly generated, such that each board has 16 distinct pictures that are equally likely to be any of the 54.

During the game, one card from the deck is drawn at a time, and anyone whose board includes that card’s picture marks it on their board. A player wins by marking four pictures that form one of four patterns, as exemplified below: any entire row, any entire column, the four corners of the grid and any 2-by-2 square.

After the fourth card has been drawn, there are no winners. What is the probability that there will be exactly one winner when the fifth card is drawn?

My solution:
[Show Solution]

Suppose $m$ players are playing the game ($m=1000$) and there are $n$ distinct cards $(n=54)$. Let’s consider the game from the point of view of one player. Define the following events:
\begin{align}
A &: \left\{\text{No winning pattern in the first four cards}\right\} \\
B &: \left\{\text{No winning pattern in the first five cards}\right\}
\end{align}If we count all the possible winning patterns, we see that there are 18. Meanwhile, there are $\binom{n}{4}$ ways of picking four cards. The probability of no winning pattern is 1 minus the probability of a winning pattern:
\[
\mathbf{P}(A) = 1-\frac{18}{\binom{n}{4}}
= \frac{35137}{35139} \approx 0.999943
\]The approach is similar when there are five cards. Each of the 18 winning patterns uses 4 cards. The fifth card can be any of the remaining $n-4$ cards, so we have:
\[
\mathbf{P}(B) = 1-\frac{18(n-4)}{\binom{n}{5}}
= \frac{35129}{35139} \approx 0.999715
\]

Now let’s ask the question: what is the probability that there is a winning pattern using all five cards given that there is no pattern in the first four cards. We can calculate this using Bayes’ rule and the law of total probability:
\begin{align}
\mathbf{P}(\bar B \mid A)
&= 1-\mathbf{P}(B\mid A) \\
&= 1-\frac{\mathbf{P}(A\cap B)}{\mathbf{P}(A)}\\
&= 1-\frac{\mathbf{P}(B)}{\mathbf{P}(A)}\\
&= \frac{8}{35137} \approx 0.00022768
\end{align}where in the third step, we used the fact that $B \subseteq A$ and therefore $A\cap B = B$ (if there is no winning pattern in the five cards, then there cannot be a winning pattern in the first four).

The problem asks us to find the probability that if $m$ players play the game and nobody wins on the fourth card, exactly one person wins on the fifth card. Let’s call this probability $q$. Since each player is playing independently, there are $m$ different people that can win, with probability $\mathbf{P}(\bar B\mid A)$, and the other $m-1$ players must lose, each with probability $\mathbf{P}(B \mid A)$. So the probability that exactly one person wins on the fifth card is:
\[
q\,=\, m \cdot \mathbf{P}(\bar B\mid A) \cdot \mathbf{P}(B\mid A)^{m-1}
= m \cdot \left( 1-\frac{\mathbf{P}(B)}{\mathbf{P}(A)} \right)\cdot \left( \frac{\mathbf{P}(B)}{\mathbf{P}(A)} \right)^{m-1}
\]Substituting the numerical values found earlier for $\mathbf{P}(A)$ and $\mathbf{P}(B)$ together with $m=1000$, we obtain:
\begin{align}
q &= 1000\left(\frac{8}{35137}\right) \left( \frac{35129}{35137} \right)^{999} \\
&= \frac{8000\cdot 35129^{999}}{35137^{1000}} \approx 0.181356
\end{align}So the probability that exactly one person out of 1000 wins on the fifth card given that nobody won on the first four cards is about 18.136%.

The general case

If we leave the expression for $q$ in terms of $n$ (number of distinct cards) and $m$ (number of players), we obtain:
\[
q = 1728m\cdot \frac{\left(n^4-6 n^3+11 n^2-6 n-2160\right)^{m-1}}{\left(n^4-6 n^3+11 n^2-6 n-432\right)^{m}}
\]If we fix $m=1000$ and vary $n$, we obtain the following graph:

When $n$ is small, it is very likely that many people will win. So the probability that only one person wins on the 5th card is low. But when $n$ is very large, it is very unlikely that anybody will ever win, so the probability that one person wins on the 5th card is low again. The peak occurs at $n=38$ (with probability 36.8%).

If instead we fix $n=54$ and vary $m$, we obtain the following graph:

The shape of the curve is similar. When $m$ is small, there are not many people, so it is not likely that anybody will win on the fifth card. But when $m$ is large, it is likely that many people will win, but unlikely that only one person will win. The peak occurs at $m=4392$ (with probability 36.8% again).

If we vary $m$ and $n$ together, we see that for each $n$, there is an ideal number of players $m$ that would maximize the probability (red dashed line in the plot below).

The red dashed curve has the equation $m = \frac{n^4-6 n^3+11 n^2-6 n-432}{1728}$.

Numerical validation

To test whether the above formulas are correct, I ran a Monte Carlo simulation to estimate $\mathbf{P}(\bar B\mid A)$, which is the probability that a single player wins on the fifth card given that they did not win on the fourth card. I simulated a large number of games and only kept those that didn’t win after four cards. Then I computed the empirical fraction of the remaining cases that won on the fifth card. Here is my Python code.

# winning sets of indices
win_idx = [
    [0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15],  # four in a row
    [0,4,8,12],[1,5,9,13],[2,6,10,14],[3,7,11,15],  # four in a column
    [0,1,4,5],[1,2,5,6],[2,3,6,7],                  # 2x2 in first row
    [4,5,8,9],[5,6,9,10],[6,7,10,11],               # 2x2 in second row
    [8,9,12,13],[9,10,13,14],[10,11,14,15],         # 2x2 in third row
    [0,3,12,15]                                     # four corners
]

# returns True if a bingo card is a winner
def iswinning(matches):
    for idx in win_idx:
        if all([matches[i] for i in idx]):
            return True
    return False

# compute the probability that 5th card wins
# given that the 4th card did not win
N = 10**7

count,total = 0,0

n = 54                   # number of cards
S = list(range(n))       # full set of numbers
C = random.sample(S,16)  # 16 chosen numbers

for iter in range(N):
    F = random.sample(S,5)   # five drawn numbers

    # bingo score card after 4 and 5 turns
    matches4 = [c in F[:-1] for c in C]
    matches5 = [c in F for c in C]
    
    if not iswinning(matches4):
        total += 1
        if iswinning(matches5):
            count += 1

# empirical probability and 95% confidence interval
phat = count/total
conf = 1.96*np.sqrt(phat*(1-phat)/total)

print(f'Analytical: {1728 / (-432 - 6*n + 11*n**2 - 6*n**3 + n**4):.5g}')
print(f'Monte Carlo: {count}/{total} = {phat:.4g}, or [{phat-conf:.4g},{phat+conf:.4g}] (95% CI)')

The result of running this code is:

Analytical: 0.00022768
Monte Carlo: 2292/9999478 = 0.0002292, or [0.0002198,0.0002386] (95% CI)

Unfortunately, since we are trying to estimate such a small probability, a large number of samples are required to reach a narrow confidence interval. I used 10 million samples in the simulation above, which took about 4 minutes on my laptop.

Desert escape

This week’s Riddler classic is about geometry and probability, and desert escape! Here is the (paraphrased) problem:

There are $n$ travelers who are trapped on a thin and narrow oasis. They each independently pick a random location in the oasis from which to start and a random direction in which to travel. What is the probability that none of their paths will intersect, in terms of $n$?

My solution:
[Show Solution]

First, consider a simpler problem, where all travelers depart from the same side of the oasis. Here is a diagram of what that might look like.

The paths will not cross precisely if the angles from left-to-right are arranged from smallest to largest. For example, in the diagram above, the paths will not cross because $\theta_1 \lt \theta_2 \lt \theta_3$. Once you fix the angles, only one of the $n!$ possible arrangements of the travelers will have the correct ordering. Therefore, the probability that the paths do not intersect is $\frac{1}{n!}$.

Now consider the case where travelers can depart from either side of the oasis. Suppose $k$ travelers depart from the top and $n-k$ depart from the bottom, as in the diagram below.

Since each traveler is equally likely to depart from either side, the probability of this happening is $\frac{1}{2^n} \binom{n}{k}$ (it’s a binomial distribution). The probability that the paths do not intersect is $\frac{1}{k!(n-k)!}$, since it is the product of the probability that the $k$ travelers departing from the top do not intersect and the $n-k$ travelers departing from the bottom do not intersect, and both events are independent. To find the total probability $P_n$, we sum over all possible $k$:
\begin{align}
P_n &= \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \frac{1}{k!(n-k)!} \\
&= \frac{1}{2^n \cdot n!} \sum_{k=0}^n \binom{n}{k} \frac{n!}{k!(n-k)!} \\
&= \frac{1}{2^n \cdot n!} \sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} \\
&= \frac{1}{2^n \cdot n!}\binom{2n}{n} \\
&= \frac{(2n)!}{2^n \cdot (n!)^3}
\end{align}The last step is a result of Vandermonde’s identity. You can think of it as counting the number of ways of picking $n$ objects from a set of $2n$ objects. We can do this by imagining that our $2n$ objects are split into two groups of $n$, and we are picking $k$ from the first group and $n-k$ from the second group, and then summing over $k$. If you are interested in these sorts of binomial identities, I encourage you to read the two-part blog post I wrote on the topic (part 1 and part 2). So when the dust settles, the probability of the paths not intersecting is:

$\displaystyle
P_n = \frac{(2n)!}{2^n \cdot (n!)^3}
$

This function decreases rapidly as $n$ increases. To see this, we can plot $P_n$ as a function of $n$. Here is what we obtain:

To get a better handle on $P_n$, we can use Stirling’s approximation to the factorial, $n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$, which yields
\[
P_n \sim \frac{1}{2\sqrt{2}\,\pi\,e} \left( \frac{2e}{n}\right)^{n+1}
\]This tells us that $\log(P_n) \sim -n\log(n)$, which agrees with the almost linear decrease of $P_n$ on a log scale.

Cutting a ruler into pieces

This week’s Riddler Classic is a paradoxical question about cutting a ruler into smaller pieces.

Recently, there was an issue with the production of foot-long rulers. It seems that each ruler was accidentally sliced at three random points along the ruler, resulting in four pieces. Looking on the bright side, that means there are now four times as many rulers — they just happen to have different lengths. On average, how long are the pieces that contain the 6-inch mark?

With four cuts, each piece will be on average 3 inches long, but that can’t be the answer, can it?

Here is my solution:
[Show Solution]

We will consider the following more general version of the problem.

Suppose a ruler of length $L$ is marked at a fraction “$a$” from one end of the ruler. Now suppose $N-1$ cuts are chosen uniformly at random along the length of the ruler, which splits the ruler into $N$ smaller pieces. What is the expected length of the piece that contains the mark?

In the original problem, $L=12\text{ inches}$, $a=\tfrac{1}{2}$, and $N=4$.

We will start by considering a simpler problem. Suppose we have $k$ numbers chosen uniformly at random and independently on the interval $[0,b]$. What is the expected value of $\min_{1\leq i \leq k} x_i$? We can compute this using the fact that:
\begin{align}
\mathbb{E}\left( \min_{1\leq i \leq k} x_i \right) &= \int_0^b \mathbf{Prob}( \min(x_i) \geq t )\,\mathrm{d}t \\
&= \int_0^b \mathbf{Prob}( x_1 \geq t, \dots, x_k \geq t )\,\mathrm{d}t \\
&= \int_0^b \mathbf{Prob}( x_1 \geq t) \cdots \mathbf{Prob}( x_k \geq t )\,\mathrm{d}t \\
&= \int_0^b \mathbf{Prob}( x_1 \geq t)^k\,\mathrm{d}t \\
&= \int_0^b \left( \frac{b-t}{b}\right)^k \mathrm{d}t \\
&= \frac{b}{k+1}
\end{align}The first equality follows from the fact that expectation can be written as the integral of the complementary cumulative distribution function (wiki link). Then, we use the fact that the $x_i$ are mutually independent and identically distributed.

Back to our original problem, we can split it into cases depending on how many cuts end up to the left vs how many end up to the right of our mark. Suppose we have $k$ cuts to the left of $a$, and the remaining $N-k-1$ cuts to the right. Then the expected length of the piece containing $a$ is the sum of the expected lengths of the “left part” and “right part”. Each of these pieces can be computed based on the preliminary result above, and we obtain:
\[
L\left(\frac{a}{k+1}+\frac{1-a}{N-k}\right)
\]Note that this formula gives the correct answer when $k=0$; it returns a length of $a$ for the left half (the whole interval). Next, we must compute the probability of this actually occurring; that exactly $k$ cuts are on the left and $N-k-1$ cuts are on the right. Since the probability of these events happening are $a$ and $1-a$, respectively, and they are mutually independent, we have a binomial distribution. The probability that $k$ cuts are to the left of $a$ is therefore:
\[
\binom{N-1}{k}a^k (1-a)^{N-k}
\]Combining these two facts, the expectation we seek to evaluate can be written as the sum:
\[
\sum_{k=0}^{N-1} L\left(\frac{a}{k+1}+\frac{1-a}{N-k}\right) \binom{N-1}{k}a^k (1-a)^{N-k-1}
\]We can split this into two separate sums. For the first one,
\begin{align}
&\sum_{k=0}^{N-1} \frac{L a}{k+1}\binom{N-1}{k}a^k (1-a)^{N-k-1}\\
&= \sum_{k=0}^{N-1} \frac{L}{N}\binom{N}{k+1}a^{k+1} (1-a)^{N-k-1} \\
&= \sum_{k=1}^{N} \frac{L}{N}\binom{N}{k}a^{k} (1-a)^{N-k} \\
&= \frac{L}{N}\left( 1-(1-a)^N \right)
\end{align}where we used the binomial theorem in the final step to evaluate the sum. Using a similar argument for the other half of the sum, we obtain $\frac{L}{N}\left( 1-a^N\right)$. Combining both parts, we find our final formula for the expected length of the piece containing the mark:

$\displaystyle
\frac{L}{N}\Bigl( 2-a^N-(1-a)^N \Bigr)
$

In particular, for the original problem statement, $L=12\text{ inches}$, $a=\tfrac{1}{2}$, and $N=4$. So the final answer is $\frac{45}{8}= 5.625\text{ inches}$. This is substantially longer than the average length of each piece, which is 3 inches.

Several interpretations of this fact were brought to my attention, so I will relay a couple here.
Commenter Guy D. Moore noted that this is an example of selection bias. My colleague Kangwook Lee also pointed out that this phenomenon is precisely the inspection paradox from probability theory.

Here is an intuitive explanation for why the true answer is so much larger than 3. The longer pieces of ruler are more likely to contain the 6-inch mark. In fact, any piece longer than 6 inches is guaranteed to contain the 6-inch mark! Although such pieces are rare, we are conditioning on the fact that our piece contains the 6-inch mark, so we are likelier to pick out these longer pieces and so the average piece length will be longer.

Limiting cases

As a sanity check, let’s see what happens when we consider the limiting behavior of our formula.

If $N=1$ (just one piece), the formula simplifies to $L$, which makes sense. In this case, no cuts are made, so all pieces contain the mark, and all pieces are of length $L$.
If $a=0$ or $a=1$ (the mark is at either end of the ruler), the formula simplifies to $\frac{L}{N}$, which is the average piece length. This makes sense because the first piece always contains the mark, and there is no reason the first piece should be any longer or shorter than the average piece.
If $N$ gets very large and $0\lt a\lt 1$, the formula tends to $\frac{2L}{N}$. So pieces containing the mark are on average twice as long as the average piece.

Here is a figure showing how much longer the marked piece of ruler is compared to the average length $\frac{L}{N}$. We can visually confirm the three limiting cases: when $N=1$, we just get the average length, if $a=0$ or $a=1$ we also get the average length, and as $N\to\infty$, we do indeed tend to $2$. The solution to the original problem ($a=\tfrac{1}{2}$ and $N=4$) produces a ratio of $1.875$, which when multiplied by the average length $\frac{L}{N} = \frac{12}{4} = 3$ produces the answer we reported above, $5.625$.

Flip to freedom

This week’s Riddler Classic is a problem about coin flipping. The text of the original problem is quite long, so I will paraphrase it here:

There are $n$ prisoners, each with access to a random number generator (generates uniform random numbers in $[0,1]$) and a fair coin. Each prisoner is given the opportunity to flip their coin once if they so choose. If all of the flipped coins come up Heads, all prisoners are released. But if any of the flipped coins come up Tails, or if no coins are flipped at all, the prisoners are not released. If the prisoners cannot communicate in any way and do not know who is flipping their coin or not, how can they maximize their chances of being released?

Here is my solution:
[Show Solution]

This problem is a balancing act. If $k$ of the prisoners flip their coins, the chance of being released is
\[
\mathrm{Prob}(\text{win if }k\text{ coins are flipped})=\begin{cases} 0 & k=0\\ \frac{1}{2^k} & k=1,2,\dots,n\end{cases}
\]The best-case scenario is if $k=1$ prisoner flips their coin and the others do not, ensuring the maximum probability of release of $1/2$. But how should the prisoners decide who flips their coin? If they were allowed to communicate ahead of time, they could elect somebody to flip their coin. But since the prisoners cannot communicate so there is no way to plan ahead!

Since each prisoner has access to a random number generator, they can use it to decide whether they should be flipping their coin or not. Here is the strategy. We must decide on a threshold $t$. Each prisoner queries their random number generator and if the number they obtain is less than $t$, they flip their coin. The larger $t$ is, the more likely prisoners are to flip coins. So there is a trade-off between ensuring at least one prisoner flips a coin and ensuring not too many prisoners flip coins. Let’s figure out the best choice of $t$.

Let’s call the probability the prisoners are released $f_n(t)$. It depends on the threshold they choose. Now,
\begin{align*}
f_n(t) &= \sum_{k=1}^n \frac{1}{2^k} \mathrm{Prob}(\text{there are }k\text{ flips}) \\
&= \sum_{k=1}^n \frac{1}{2^k} \binom{n}{k}t^k(1-t)^{n-k} \\
&= \sum_{k=1}^n \binom{n}{k}\left(\frac{t}{2}\right)^k (1-t)^{n-k} \\
&= ( 1-\tfrac{1}{2}t)^n-(1-t)^n
\end{align*} In the last step, we used the Binomial Theorem to evaluate the sum. So our goal is to find $t\in[0,1]$ that minimizes $f_n(t)$. Here is what the function looks like for different values of $n$:

As anticipated, there is an ideal value of the threshold $t$ that maximizes the probability of winning. However, the maximum depends on $n$, the number of prisoners. To find the maximum, we can use calculus: set the derivative of $f_n(t)$ equal to zero:
\[
\frac{\mathrm{d}f_n(t)}{\mathrm{d}t}=n(1-t)^{n-1}-\tfrac{1}{2}n(1-\tfrac{1}{2}t)^{n-1}=0
\]Solving for the optimal threshold $t$, we obtain:

$\displaystyle
t_\text{opt}=1-\frac{1}{2^{n/(n-1)}-1}
$

As a function of $n$, $t_\text{opt}$ is the threshold each prisoner should use. If their random number generator produces a value less than the threshold, they should flip their coin. Otherwise, they should not. As anticipated, in the limit $n\to\infty$, $t_\text{opt}\to 0$ because as the number of prisoners increases, we want each prisoner to be less likely to flip their coin. As an approximation, the first order asymptotic expansion of $t_\text{opt}$ is
\[
t_\text{opt} = \frac{2\log(2)}{n} + O\left(\frac{1}{n^2}\right)\approx\frac{1.386}{n}
\]So this can be used as a quick way to approximate the threshold (in case the prisoners don’t have access to a calculator!).

How about the probability of winning assuming the prisoners use this strategy? This simply amounts to evaluating $f_n(t_\text{opt})$. Doing so, we obtain:

$\displaystyle
\textrm{Prob}(\text{win}) = \frac{1}{\left(2^{n/(n-1)}-1\right)^{n-1}}
$

Here is a table comparing the optimal threshold and corresponding probability of winning for different values of $n$:

Number of prisoners	threshold $t_\text{opt}$	Probability of freedom
1	1	0.5
2	0.666667	0.333333
3	0.453082	0.299119
4	0.342037	0.284842
5	0.274529	0.277001
10	0.13802	0.262709
50	0.0277034	0.252429
100	0.0138574	0.251208

So when $n=1$, the lone prisoner flips every time and the probability of winning is $\frac{1}{2}$. With two prisoners, each prisoner should flip $\frac{2}{3}$ of the time, and the probability of winning is $\frac{1}{3}$. As $n\to\infty$, the threshold goes to zero as described above, and we can also verify that the probability of winning tends to $\frac{1}{4}$ in the limit.

So this strategy ensures that the probability of all prisoners being released is always at least 25%. The only caveat is that in order to compute which threshold to use, the prisoners must know $n$, the total number of prisoners playing the game.

Mismatched socks

This week’s Riddler Classic is a problem familiar to many…

I have $n$ pairs of socks in a drawer. Each pair is distinct from another and consists of two matching socks. Alas, I’m negligent when it comes to folding my laundry, and so the socks are not folded into pairs. This morning, fumbling around in the dark, I pull the socks out of the drawer, randomly and one at a time, until I have a matching pair of socks among the ones I’ve removed from the drawer.

On average, how many socks will I pull out of the drawer in order to get my first matching pair?

Here is my solution:
[Show Solution]

Computing the expectation

Define $T$ to be number of turns that the game lasts (this is a random variable). Define $q_k = \textbf{P}(T > k)$ to be the probability that the game has still not ended after $k$ draws. We can compute this explicitly. There are $\binom{2n}{k}$ possible (equally likely) ways of choosing $k$ socks among the $2n$ socks in the drawer. If there is no match, we must have drawn $k$ socks of different colors. There are $\binom{n}{k}$ ways to choose the $k$ colors and $2^k$ ways to pick the socks once the colors are chosen. Putting everything together and performing some algebraic manipulations, we obtain:
\[
q_k = \frac{\binom{n}{k} 2^k}{\binom{2n}{k}}
= \frac{n! \cdot (2n-k)! \cdot 2^k}{(2n)! \cdot (n-k)!}
= \frac{ \binom{2n-k}{n} 2^k }{\binom{2n}{n}}
\]Let’s also define $p_k = \textbf{P}(T=k)$ to be the probability that the game ends on precisely the $k^\text{th}$ draw. Note that $q_{k} = p_{k+1}+p_{k+2}+\cdots+p_{n+1}$, or alternatively, $p_k = q_{k-1}-q_k$. From the definition of expected value:
\[
\textbf{E}(T) = \sum_{k=1}^{n+1} k\,p_k = \sum_{k=1}^{n+1}k(q_{k-1}-q_k) = \sum_{k=0}^n q_k
\]This is a manifestation of the general fact that $\textbf{E}(T) = \sum_{k\ge 0}\textbf{P}(T > k)$. Make the change $k\mapsto n-k$ in the expectation:
\[
\textbf{E}(T) = \frac{\sum_{k=0}^n \binom{2n-k}{n} 2^k}{\binom{2n}{n}}
= \frac{2^n \sum_{k=0}^n \binom{n+k}{k} 2^{-k}}{\binom{2n}{n}}
\]Consider the sum in the numerator. Define:
\[
S_n = \sum_{k=0}^n \binom{n+k}{k} 2^{-k}
\]We can evaluate this sum recursively:
\begin{align}
S_{n+1} &= \sum_{k=0}^{n+1} \binom{n+k+1}{k} 2^{-k} \\
&= \sum_{k=0}^{n+1}\left[ \binom{n+k}{k} + \binom{n+k}{k-1} \right] 2^{-k} \\
&= \sum_{k=0}^{n+1} \binom{n+k}{k}2^{-k} + \sum_{k=0}^{n+1} \binom{n+k}{k-1} 2^{-k} \\
&= S_n + \binom{2n+1}{n+1}2^{-n-1} + \sum_{k=0}^{n} \binom{n+k+1}{k} 2^{-k-1} \\
&= S_n + \tfrac{1}{2}S_{n+1}
\end{align}Solving, we obtain $S_{n+1} = 2S_n$, and therefore conclude that $S_n = 2^n$. Substituting this result back into the formula we had above, we obtain:

$\displaystyle
\textbf{E}(T) = \frac{4^n}{\binom{2n}{n}}
$

To get a feel for how this expression varies with $n$, we can use Stirling’s approximation, which leads us to the approximation:
\[
\textbf{E}(T) \approx \sqrt{\pi n}
\]So the expected number of socks we’ll have to draw grows as the square root of the number of pairs. For example, when we have $n=10$ pairs of socks, $\textbf{E}(T) = \frac{262144}{46189}\approx 5.67546$. Meanwhile, the approximation yields $\sqrt{10\pi} \approx 5.60499$. The approximation gets better as $n$ gets larger. Here is a plot showing the true expected value and the approximation:

Computing the distribution

We have the expectation $\textbf{E}(T) = \frac{4^n}{\binom{2n}{n}} \approx \sqrt{\pi n}$. But what about the distribution of $T$ itself? Does it approach anything interesting as $n$ gets large? First, we need to compute the exact probability mass function, which is nothing other than $p_k$. We can do this from the recursion we derived earlier: $p_k = q_{k-1}-q_k$. This simplifies to:
\[
p_k = \frac{k-1}{n-k+1} \frac{\binom{2n-k}{n} 2^{k-1} }{\binom{2n}{n}}\qquad\text{for }k=1,2,\dots,n+1
\]We can plot these distributions along with their means to see what it looks like. Here are the distributions of $T$ for $n=\{10,20,50,100\}$.

To understand what this distribution looks like as $n$ gets very large, we have to do a bit of asymptotic analysis. This part is a little rough around the edges (read: not particularly rigorous), but it seems to give a reasonable answer. My reasoning was that as $n\to\infty$, $k$ is small compared to $n$ because the mean grows like $\sqrt{n}$. Therefore, we will assume $k \sim \sqrt{n}$.

Using Mathematica, we can look at how $\frac{p_k}{k-1}$ varies for small $k$. Using a series approximation about $k=0$ and $n=\infty$, we find that:
\[
\log\left( \frac{p_k}{k-1} \right) \approx \log(\tfrac{1}{2n}) + O(\tfrac{1}{n}) + \tfrac{5}{4n} k-\tfrac{1}{4n}k^2+O(k^3)
\]Therefore, we conclude that:
\[
p_k \approx \frac{k}{2n} e^{-\tfrac{k^2}{4n}}
\]This means that as $n\to\infty$, the distribution of stopping time $T$ approaches a Rayleigh distribution with parameter $\sigma = \sqrt{2n}$. This also gives the correct mean for large $n$, as the mean of the Rayleigh distribution is $\sigma\sqrt{\frac{\pi}{2}} = \sqrt{\pi n}$. For a comparison, here is the plot for $n=500$ along with the Rayleigh approximation: