Another timely election-related Riddler problem. What are the odds of being the deciding vote?

You are the only sane voter in a state with two candidates running for Senate. There are N other people in the state, and each of them votes completely randomly! Those voters all act independently and have a 50-50 chance of voting for either candidate. What are the odds that your vote changes the outcome of the election toward your preferred candidate?

More importantly, how do these odds scale with the number of people in the state? For example, if twice as many people lived in the state, how much would your chances of swinging the election change?

Here is my solution:

[Show Solution]

In order for somebody to be the deciding vote, the $N$ other votes must be perfectly split. Let’s call the probability of this occurring $p(N)$. Because of the independence assumption, $p(N)$ is the same as the probability of flipping $N$ fair coins and having exactly half of them land Heads. The number of Heads obtained follows a Binomial distribution. Therefore,

\[

p(N) = \frac{1}{2^N} {N \choose \frac{N}2 }

\]It isn’t particularly clear what happens as $N$ gets large, so we can make use of the handy Stirling approximation. The result is that:

\[

p(N) \approx \sqrt{\frac{2}{\pi}} \frac{1}{\sqrt{N}}

\]So the odds scale like $1/\sqrt{N}$. In other words, every time the population quadruples, you’re half as likely to be the deciding vote. We can check this by directly applying the formula. If the population is 100,000 your probability of being the deciding vote is 0.2523%. If the population is 400,000 the probability shrinks to 0.1262%, as expected.

Here is a plot of the probability as a function of population size.

Because of the $1/\sqrt{N}$ dependence, the graph is a line of slope $-1/2$ when plotted on log-log axes.

And if N is odd, $p(N) = \frac{1}{2^N} {N \choose \frac{N-1}2 }$ regardless of how the ties are handled.

Yes, and we can find the first subleading correction, giving

p(N) = sqrt(2/pi N) ( 1 – 1/4N ) for N even, (1 – 3/4N) for N odd

which improves the fit for small N (and invisibly for large N).