This week, I attempted the Riddler Classic:

Say 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?

My initial hypothesis was 50%. The problem could be reworded this way: given a certain number of coin-flips, what is the likelihood that the count of heads (or tails for that matter) will equal exactly half of the total coin-flips?

I immediately regretted my first hypothesis, because – what if there are an odd number of coin-flips? It’s impossible to have a 50-50 split. So I re-read the question to see if I was thinking about it correctly. “What are the odds that your vote changes the outcome of the election toward your preferred candidate?” So, I assumed that switching a Win for my opponent to a Tie would qualify. Ok. So a result of “behind by 1 vote if there are an odd number of voters” is also a positive outcome.

Next, I drew up a spreadsheet to map out all the outcomes if there were 4 voters. That seemed like a low-enough number to wrap my head around, but also high enough, so as not to be trivial.

Huh. 6/16 or 3/8.

Let try more voters. How about 5. So there are 32 possible outcomes of the other 5 voters. But what happens when the vote is 3-2? Well, then it matters which color you’d vote for! In fact, that’s the only case in which your vote would matter. So, that adds another column to our table – which looks a lot like what you’d expect the table for 6 voters to look like!

8 Voters!

Well, the denominator is easy enough to calculate: 2^{n}. But I still wasn’t catching on to the pattern for the numerator.

10 Voters!

Ok. Fine! It had to hit me over the head with a hammer, but I finally got it. Pascal’s Triangle. Sheesh, it’s embarrassing that it took so long to recognize it. Oh well.

So for any given number of voters, find that row in Pascal’s Triangle (for odd rows, go to row+1), and find the middle number, and that’s the number of scenarios in which your vote will decide the outcome. This number can also be calculated by: “n choose (n/2)” or “n!/(n/2)!*(n/2)!” or “n!/((n/2)!)^{2} (See Combination for more info).

As I could see (and assume), the more people who vote, the less likely it is that your vote will decide the outcome. That just makes sense. But now we have a formula for defining exactly how probable it is that you will matter.

For n = the number of voters…

n!/((n/2)!)^{2}

—————–

2^{n}

All of the screenshots from this post are from this spreadsheet, which also has an “Answers” tab which calculates this formula for even numbers between 4 and 100.