Riddler Classic: How Far Would You Go To Rig A Coin Flip?

An Election Probability Riddler Classic, Just in Time for November 6

two math puzzles to end your week right: https://t.co/ty6CpcrWXK pic.twitter.com/9EnPlGbwEt

— Oliver Roeder (@ollie) November 2, 2018

This week’s FiveThirtyEight Riddler Classic was about winning elections, fair and square, or by any means necessary… In this case, it’s Programmers versus Theorists, and elections are decided by flipping coins for each of one hundred Senate seats. As an analyst for Riddler Nation’s wildly successful data-driven political blog, OneHundred, these are the questions we are confronted with today:

Question 1: What is the probability that one party will win a simple majority?

senators <- 51:100
sum(choose(100, senators)) * (1/2)^100

senators <- 60:100
sum(choose(100, senators)) * (1/2)^100

Question 2: what weighting would give them a 50% chance of winning a 60-seat supermajority?

From equation (1), must solve for p such that: \[ \frac{1}{2}=\sum_{k=60}^{k=100}\binom{100}{k}p^{k}(1-p)^{100-k} \] Find the root in (0, 1) of: \[ \sum_{k=60}^{k=100}\binom{100}{k}p^{k}(1-p)^{100-k}-\frac{1}{2}=0 \]

senators <- 60:100
weighting <- function(x) sum(choose(100, senators) * (x^senators) * (1-x)^(100-senators)) - 0.5
result <- uniroot(weighting, c(0,1))
result$root

[1] 0.5947

qbinom(c(0, 0.99), size=100, prob=0.5)

qbinom(c(0, 0.99), size=200, prob=0.5)

Question 3: If the Programmers decide to cheat by weighting the coin permanently for the next 100 elections, how heavily can they weight it and escape a 99% challenge by the Theorists?

Over 100 years there will be 10,000 separate coin flips. The 99th-percentile of this binomial distribution is 5,116. This implies they can cheat by giving themselves a probability p up to 0.5116

qbinom(c(0, 0.99), size=10000, prob=0.5)

[1] 0 5116

p <- 0.5116
senators <- 60:100
sum(choose(100, senators) * (p^senators) * (1-p)^(100-senators))

100 * sum(choose(100, senators) * (p^senators) * (1-p)^(100-senators))

Question 4: What is the optimal cheating strategy for the Programmers?

We calculate for each year the cumulative 99th percentile of coin flips the Programmers can win while remaining “innocent” before the Statistical Court. We subtract one from that amount and determine the required coin weight to produce those expected wins.

optimal <- as.data.frame(matrix(NA,nrow=125,ncol=5))
colnames(optimal) <- c('Year','quantile','opt','diff','Weight')
optimal$Year <- 1:125
optimal$quantile <- qbinom(0.99, size=100*optimal$Year, prob=0.5)
optimal$opt <- optimal$quantile-1
optimal$diff[2:125] <- diff(optimal$opt); optimal$diff[1] <- 61
optimal$Weight <- optimal$diff/100

We notice an interesting oscillatory pattern where after cravenly cheating for over 30 years, the Programmers’ coin needs to be fair in a growing proportion of elections over time. When they have enough “buffer”, the Programmers can cheat for an election, or two, before returning to a fair coin.

Question 5: Does changing the coin weight on a seat-by-seat basis help improve the Programmers’ odds in any of these scenarios?

No, it wouldn’t because the Theorists are checking the election results on an election-by-election basis, based on the number of seats won by the Programmers, which is an integer value that must be within the 99th percentile of a binomial distribution. Setting different win probabilities by seat does not change the check of the overall election.

Addendum

As Riddler Nation star @laurentLessard pointed out, there is some ambiguity in the wording of these questions that necessitate some clarification:

I get that, but the result of your statistical test will depend on what the flips actually turn out to be. In general, anything could happen. The number of years you can rig the system will depend on how lucky or unlucky you've been so far in the outcones of the actual flips.

— Laurent Lessard (@LaurentLessard) November 2, 2018

In particular, the above results for questions 3-5 hold in an expected value sense, but not necessarily in a realized sense. Specifically, the Programmers may cheat by weighting the coin in a favorable way and still fail to beat the Theorists. There is also the possibility that they nay tilt the odds in their favor more than the “optimal” and still fail to be detected. Anything could happen, but the calculations above should hold “on average”, if there were thousands of Riddler Nations out there.