Twice is always nice, so I’m going to tackle the Classic Riddler for the week as well.

For those that aren’t familiar, The Riddler is a weekly puzzle series from Oliver Roeder at FiveThirtyEight that usually involves some combination of math, logic and probability.

This weeks Riddler Classic is:

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?

As with most other Riddler problems, I want to start with doing some of the basic cases when N is low. As per our friend at 538, Ollie, we’ll deal with ties as such:

@ianrhile assume a coin flip if you’d like. or just assume an odd number of voters.

— Oliver Roeder (@ollie) November 4, 2016

So let’s start with the basic case of N=1 (1 other voter). The voter can either vote for your preferred candidate (D) or your non-preferred candidate (R). You’ll always be voting for your preferred candidate (D). Our goal is to find out what percent of the time that will make a difference. So let’s take a look at the scenarios that could happen:

Scenario |
Votes D |
Votes R |
Chance of Scenario |

A | 1 | 0 | 0.5 |

B | 0 | 1 | 0.5 |

Pretty simple. In Scenario A, your candidate’s winning, so your vote for candidate D doesn’t matter. If Scenario B happens, you can force a tie, which according to Ollie goes to a coin flip. So the probability of you affecting the election (P_{1}) is:

P_{1}= (Probability of Scenario B)*(Probability that Tiebreaker Coinflip Lands in Your Favor)

P_{1}= 0.5 *0.5 =0.25

Simple enough, let’s look at P_{2}. The voters here can either go DD (both vote for D), RR, DR, or RD. Since the last two states are the same for our purposes, we can sum up the system at N=2 as:

Scenario |
Votes D |
Votes R |
Chance of Scenario |

A | 2 | 0 | 0.25 |

B | 0 | 2 | 0.25 |

C | 1 | 1 | 0.5 |

In Scenario A , your candidate won, so it doesn’t really matter to us. In Scenario B, your 1 vote for Candidate D won’t influence the result so that’s not relevant either. So we look at Scenario C, however there’s no coinflip element here therefore:

P

_{2}= Probability of Scenario C =0.5

Let’s jump ahead to N=5 so we can deal with a more interesting scenario. The states that can exist at N=5 are:

Scenario | Votes D | Votes R | Chance of Scenario |

A | 0 | 5 | 0.03125 |

B | 1 | 4 | 0.15625 |

C | 2 | 3 | 0.3125 |

D | 3 | 2 | 0.3125 |

E | 4 | 1 | 0.15625 |

F | 5 | 0 | 0.03125 |

There’s two important things to notice here. There’s really only one scenario where we can affect the result in our favor (Scenario C, where we can force a tie). By now we see a pattern in the types of scenarios that our vote can influence – we can either force a tie as shown in Scenario C for N=5 or break a tie as shown in Scenario C for N =3 earlier. Those situations can be defined as:

Situations Where Our Vote Matters = [N/2]

The nearest integer function (as denoted by [x]) rounds down a number to nearest integer (e.g. [2.5] = 2). Cool, now we know for a given N which scenarios we can actually influence.

Before N=5, calculating the probability was rather trivial. For larger N we can fall back on the Binomial Probability Formula defined by:

P

_{k successes in n trials}= nCr(n,k)*p^{k}*(1-p)^{n-k}

Each of those terms are:

nCr(n,k) = Amount of unordered combinations for a given k objects in set of n total objects (e.g. how many unique ways can you have 2 heads given 5 coins). Defined by n!/((n-k)!*k!).

k = Successes. For our problem, that’ll be votes cast for Candidate D

p = Probability of success

Since we’re dealing with 50/50 odds, a lot of that formula can get simplified. Also, we defined the scenarios that we can affect as ones where Canidate D votes = [N/2], therefore k = [N/2]. That results in the simplified formula:

P_{k successes in n trials}= nCr(n,k)*p^{k}*(1-p)^{n-k}= nCr(n,k)*0.5^{k}*(0.5)^{n-k}= nCr(n,k)*0.5^{k+n-k}= nCr(n,k)*0.5^{n }=nCr(n,[n])*0.5^{n }P

_{Scenario our vote counts @ given N}=N!/((N-[N/2])!*[N/2]!)*0.5^{N}

Recall that at odd N’s our vote just forced a tie in this scenario, and we had to account for . So in actuality, the general solution is a bit disjointed. The solution is:

For Even N

P_{Even N} = **N!/((N-[N/2])!*[N/2]!)*0.5 ^{N}**

For Odd N

P_{Odd N} = **0.5*N!/((N-[N/2])!*[N/2]!)*0.5 ^{N}**

This relationship can be described in the following graphs:

Dear Rob, this was a fun read. Good work. Although, in the following line,

Pk successes in n trials = nCr(n,k)*pk*(1-p)n-k = nCr(n,k)*0.5k*(0.5)n-k = nCr(n,k)*0.5k+n-k = nCr(n,k)*0.5n = nCr(n,[n])*0.5n

you replaced k with [n] — don’t you mean [n/2]?

bhargs