This is my solution to the Five Thirty Eight Riddler for November 4.
(Note: Here’s a .pdf version of what is written below.)
It’s first important to note that N (the number of the people in the state) must be odd. If I am to decide the election, the votes must be split 50-50 with my vote left. We will therefore write $latex N = 2K + 1$. So, the population in my state (not including me) is $latex 2K$.
Now the question can be rephrased as the following: Given $latex 2K$ coin flips, what is the probability that we obtain exactly K heads? In general, there are $latex 2^{2K}$ possible outcomes of $latex 2K$ coin flips, but it is quick to check a few small cases. Here are the possibilities for two and four coin flips. (Below H denotes heads and T denotes tails.)
- Two Flips: There are four possibilities: HH, HT, TH, TT. In this case, I decide the election in two of the four possibilities (HT and TH), or 50% of the time.
- Four Flips: There are 16 possibilities. We will only write the relevant possibilities: HHTT, HTHT, HTTH, THHT, THTH, TTHH. In this case, I decide the election in six of 16 cases, or 37.5% of the time.
This approach to the problem quickly gets tedious! Fortunately, probability theory comes in handy. When an experiment has exactly two equally likely outcomes, the probability of exactly $latex X=K$ successes (or heads) in $latex 2K$ experiments follows a binomial distribution. It is exactly this probability that describes the percentage of time I will play the role of the tie-breaker! That probability is
$latex
\displaystyle
P(X=K\ \text{successes};\, 2K\ \text{experiments}) = \binom{2K}{K} \frac{1}{2^{2K}}
$
where
$latex
\displaystyle
\binom{2K}{K} = \frac{(2K)!}{(2K-K)!(K)!} = \frac{(2K)!}{(K!)^2}
$
is the binomial coefficient. Now, this expression simplifies in terms of the Gamma Function, $latex \Gamma(z)$ as
$latex
\displaystyle
P(X=K;\, 2K) = \frac{\Gamma(K + 1/2)}{\sqrt{\pi}\, \Gamma(K + 1)}
$
One standard property of the Gamma Function is that $latex \Gamma(z + 1) = z \Gamma(z)$. Applying this property, we can simplify the probability as
$latex
\displaystyle
P(X=K;\, 2K) = \frac{\Gamma(K + 1/2)}{\sqrt{\pi K}\, \Gamma(K) \sqrt{K}}
$
Now, on first glance, it looks like we have not actually simplified the expression. However, a useful property of the Gamma Function is that
$latex
\displaystyle
\lim_{n \to \infty} \frac{\Gamma(n + \alpha)}{\Gamma(n) \alpha^n} = 1
$
for any $latex \alpha \in \mathbb{R}$. This means that for $latex K$ large, the probability is
$latex
\displaystyle
P(X=K;\, 2K) \sim \frac{1}{\sqrt{\pi K}} = \sqrt{\frac{2}{\pi N}}
$
This asymptotic approximation answers the scaling question, also. Namely, if the population doubles, the probability decreases by a factor of $latex \sqrt{2}$.
