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:

Took along hia­tus from the Rid­dler, but I’m back!

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 FiveThir­tyEight Rid­dler, How Many Bananas Does it Take to Lead a Camel to Mar­ket?:

sYou have a camel and 3,000 bananas. (Because of course you do.) You would like to sell your bananas at the bazaar 1,000 miles away. Your loy­al camel can car­ry at most 1,000 bananas at a time. How­ev­er, it has an insa­tiable appetite and quite the nose for bananas — if you have bananas with you, it will demand one banana per mile trav­eled. In the absence of bananas on his back, it will hap­pi­ly walk as far as need­ed to get more bananas, loy­al beast that it is. What should you do to get the largest num­ber of bananas to the bazaar? What is that number?

So just in order to get to the mar­ket, you need a min­i­mum of 1,000 bananas, and since that just gets you there with­out any bananas to sell, a more cre­ative solu­tion is required. Let’s say we split the 3,000 bananas into 3 piles — Pile A, Pile B, & Pile C. From there we move Pile A one mile, go back and do the same for Piles B & C.

This won’t get us any­where, since at mile 1,000 we’ll be left with 0 bananas in each. Let’s instead redis­trib­ute the Pile C bananas to Pile A and Pile B.

Now if we were to just move each pile for­ward with­out redis­tri­b­u­tion we’d end up with 2 bananas to sell at the mar­ket (1 from Pile A and 1 from Pile B). Let’s redis­trib­ute the bananas every mile, now it looks like:

A pat­tern starts to emerge, every mile takes 3 bananas, specif­i­cal­ly from Pile C. For now, let’s say:

Bananas in Pile C = 1000 — 3*Miles Traveled

Now let’s look at Mile 333, about when Pile C would be exhausted.

Since we only have 1 banana left in Pile C, we can’t redis­trib­ute it. So we’re now 667 miles away from our des­ti­na­tion, with 2 piles of 1,000 bananas each. Let’s con­tin­ue this redis­tri­b­u­tion strat­e­gy with Piles A and Pile B (redis­trib­ut­ing Pile B)

Now anoth­er pat­tern emerges for Pile B. The amount of bananas in Pile B can be described as:

Bananas in Pile B = 1000 — 2*(Miles Traveled-333)

Using this we see that Pile B runs out bananas around mile 833.

At this point, we can sim­ply just car­ry Pile A, feed­ing a banana to the camel every mile for the last 177 miles. The amount of bananas left when we reach the mar­ket is sim­ply 1000 — 177 = 833.

To answer the orig­i­nal Rid­dler ques­tion, the largest amount of bananas that we can get to the bazaar under the cur­rent cir­cum­stances is 833.