Author:

Twice is always nice, so I’m going to tack­le the Clas­sic Rid­dler for the week as well.

For those that aren’t famil­iar, The Rid­dler is a week­ly puz­zle series from Oliv­er Roed­er at FiveThir­tyEight that usu­al­ly involves some com­bi­na­tion of math, log­ic and probability.

This weeks Rid­dler Clas­sic is:

You are the only sane vot­er in a state with two can­di­dates run­ning for Sen­ate. There are N oth­er peo­ple in the state, and each of them votes com­plete­ly ran­dom­ly! Those vot­ers all act inde­pen­dent­ly and have a 50–50 chance of vot­ing for either can­di­date. What are the odds that your vote changes the out­come of the elec­tion toward your pre­ferred candidate?

More impor­tant­ly, how do these odds scale with the num­ber of peo­ple in the state? For exam­ple, if twice as many peo­ple lived in the state, how much would your chances of swing­ing the elec­tion change?

As with most oth­er Rid­dler prob­lems, I want to start with doing some of the basic cas­es 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 num­ber of voters.

— Oliv­er Roed­er (@ollie) Novem­ber 4, 2016

So let’s start with the basic case of N=1 (1 oth­er vot­er). The vot­er can either vote for your pre­ferred can­di­date (D) or your non-pre­ferred can­di­date ®. You’ll always be vot­ing for your pre­ferred can­di­date (D). Our goal is to find out what per­cent of the time that will make a dif­fer­ence. So let’s take a look at the sce­nar­ios that could happen:

Pret­ty sim­ple. In Sce­nario A, your can­di­date’s win­ning, so your vote for can­di­date D does­n’t mat­ter. If Sce­nario B hap­pens, you can force a tie, which accord­ing to Ollie goes to a coin flip. So the prob­a­bil­i­ty of you affect­ing the elec­tion (P₁) is:

P₁ = (Prob­a­bil­i­ty of Sce­nario B)*(Probability that Tiebreak­er Coin­flip Lands in Your Favor)

P₁ = 0.5 *0.5 = 0.25

Sim­ple enough, let’s look at P₂. The vot­ers here can either go DD (both vote for D), RR, DR, or RD. Since the last two states are the same for our pur­pos­es, we can sum up the sys­tem at N=2 as:

In Sce­nario A , your can­di­date won, so it does­n’t real­ly mat­ter to us. In Sce­nario B, your 1 vote for Can­di­date D won’t influ­ence the result so that’s not rel­e­vant either. So we look at Sce­nario C, how­ev­er there’s no coin­flip ele­ment here therefore:

P₂ = Prob­a­bil­i­ty of Sce­nario C = 0.5

Let’s jump ahead to N=5 so we can deal with a more inter­est­ing sce­nario. The states that can exist at N=5 are:

There’s two impor­tant things to notice here. There’s real­ly only one sce­nario where we can affect the result in our favor (Sce­nario C, where we can force a tie). By now we see a pat­tern in the types of sce­nar­ios that our vote can influ­ence — we can either force a tie as shown in Sce­nario C for N=5 or break a tie as shown in Sce­nario C for N =3 ear­li­er. Those sit­u­a­tions can be defined as:

Sit­u­a­tions Where Our Vote Mat­ters = [N/2]

The near­est inte­ger func­tion (as denot­ed by [x]) rounds down a num­ber to near­est inte­ger (e.g. [2.5] = 2). Cool, now we know for a giv­en N which sce­nar­ios we can actu­al­ly influence.

Before N=5, cal­cu­lat­ing the prob­a­bil­i­ty was rather triv­ial. For larg­er N we can fall back on the Bino­mi­al Prob­a­bil­i­ty For­mu­la defined by:

P_{k suc­cess­es in n tri­als} = nCr(n,k)*p^k*(1‑p)^n‑k

Each of those terms are:

nCr(n,k) = Amount of unordered com­bi­na­tions for a giv­en k objects in set of n total objects (e.g. how many unique ways can you have 2 heads giv­en 5 coins). Defined by n!/((n‑k)!*k!).

k  = Suc­cess­es. For our prob­lem, that’ll be votes cast for Can­di­date D

p = Prob­a­bil­i­ty of success

Since we’re deal­ing with 50/50 odds, a lot of that for­mu­la can get sim­pli­fied. Also, we defined the sce­nar­ios that we can affect as ones where Canidate D votes = [N/2], there­fore k = [N/2]. That results in the sim­pli­fied formula:

P_{k suc­cess­es in n tri­als} = 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ⁿ  = nCr(n,[n])*0.5ⁿ 

P_{Sce­nario our vote counts @ giv­en N} = N!/((N-[N/2])!*[N/2]!)*0.5^N

Recall that at odd N’s our vote just forced a tie in this sce­nario, and we had to account for . So in actu­al­i­ty, the gen­er­al solu­tion is a bit dis­joint­ed. The solu­tion 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 rela­tion­ship can be described in the fol­low­ing graphs: