Riddler Classic – 11/2/2018

This week’s Riddler on FiveThirtyEight is about statistics. I had time this weekend to take a stab at a solution. The problem can be found here.

Background – Shall We Play a Game?

The key to the solution is to recognize that the repeated coin flips follow a binomial distribution. The easiest way to work with binomial distributions with a large number of trials is to approximate the binomial distribution with a normal distribution.

For a binomial distribution with $n$ trials, probability of success $p$ and probability of failure $q = 1-p$, the parameters of the approximating normal distribution are $\mu = np$ and $\sigma = \sqrt{npq}$.

The solution requires that we calculate some probabilities using the normal distribution. When approximating a binomial distribution, it is required that we apply a continuous correction for the approximations. For example, when calculating the probability that there are greater than or equal to 51 seats won, we will actually calculate the probability that the normal distribution is greater than 50.5. Several of the problems require the calculation that one party wins at least 60 seats. We will calculate when the approximating normal distribution is greater than 59.5.

I am old school enough to use a table for calculating probabilities with a normal distribution. To calculate the probability with a table, first calculate the $z$-score with the formula below.

$z = \frac{x - \mu}{\sigma}$

The table I am using shows the probability that $z$ is less than a given value. To find the probability that $z$ is greater than a given value, I will subtract the table probability from 1.

The other background material required for the solution to the riddler is on hypothesis testing. Hypothesis testing is usually taught at the end of an introduction to statistics course. I will quickly summarize the required steps for this problem.

In the problem, the Theorists will claim that the coin flips are not fair, that is $p \neq 0.5$. This forms the alternative hypothesis. The null hypothesis is that $p = 0.5$. We will be performing a two-tail proportion test with 99% confidence. To perform the test, we will calculate the test statistic below.

$\displaystyle z=\frac{\hat{p}-p}{\sqrt{\frac{p q}{n}}}$

If the test parameter is less than the critical value 2.575, then the test says to fail to reject the null hypothesis. That is, the Programmers get away with rigging the election. Otherwise, the hypothesis test says to reject the null hypothesis. In this case, the Programmers get caught.

To save some algebra steps going forward, since $p = q = 0.5$ for this problem, we will simplify the test statistic to be as below. Here, $n$ is the number of coin flips and $\hat{p}$ is the observed proportion of Programmer wins.

$\displaystyle z = 2\sqrt{n}(\hat{p} - 0.5)$

Part One – Why Can’t We All Just Get Along?

The first part asks what to expect if the coin flipping is fair. Specifically, how often will the Programmers get a simple majority or a supermajority of 60 seats. To solve this problem, we will use $z$-scores to calculate probabilities with the normal distribution.

Because the coin flip is fair, the parameters for the approximating normal distribution are $\mu = 0.5 \cdot 100 = 50$ and $\sigma = \sqrt{100 \cdot 0.5 \cdot 0.5} = 5$. Let $x$ be the number of seats won by the Programmers. Our goal is to calculate $P(x > 50.5)$ for a simple majority and $P(x > 59.5)$ for a supermajority. This is equivalent to $P(z > 0.1) = 0.4602$ and $P(z > 1.9) = 0.0287$. So, over 100 elections, the Programmers should have a simple majority 46.02 times and a supermajority 2.87 times.

Part Two – The Lamentations of Their Women

In the second part, the Programmers ask what is best in life. The goal is to rig the system so that they have a greater than 50% chance of a supermajority. To solve for the probability of a coin, we will have to find the mean and standard deviation to make the $z$-score negative. This sets up the inequality below.

$\frac{59.5 - \mu}{\sigma} < 0$

Using the substitution $\mu = 100p$ gives the solution $p > 0.5950$.

To find how long the Programmers can get away with this coin probability, we need to solve the inequality below for $n$.

$2 \sqrt{n} (0.5950 - 0.5) < 2.575$

The solution is $n < 183.7$. Thus, this scheme will work for only one full election.

Part Three – Keep Your Friends Close

For the third part, the Programmers decide to try to keep their cheating on the down low for 100 years. They want to find the largest probability they can set for the coin to avoid detection over the century, which is 10,000 coin flips.

To solve this part, we need to solve the inequality below for $\hat{p}$.

$2\sqrt{10000}(\hat{p} - 0.5) < 2.575$

The solution is $\hat{p} < 0.512875$.

The other piece of this part is to find how many supermajorities the Programmers can expect over ten decades of deceit. To perform this calculation, we will use a normal distribution with parameters $\mu = 100 \cdot 0.512875 = 51.2875$ and $\sigma = \sqrt{100 \cdot 0.512875 \cdot 0.48725} = 0.49965$. The $z$-score corresponding to $x=59.5$ is 1.6437. Thus $P(x > 59.5) = 0.0505$. The Programmers should expect about 5.05 supermajorities over 100 years, up from 2.87 if they were playing fair.

Part Four – One Hundred Years of Solitude (For the Theorists)

The fourth part is where I put behind my firm footing. The goal is to develop a long-term strategy to maintain an advantage over the Theorist and not get caught. My strategy focuses on not getting caught, but I’m not sure if it is optimal.

The main idea is to start with the largest possible probability in the first year and decrease it each year afterward. As more election results are collected, it will be easier for the Theorists to detect the cheating.

Through out this part, let $k$ be the number of the current election, starting at 1, and $s_k$ be the cumulative number of seats won by the Programmers before election $k$. The number of coin flips after election $k$ is $n = 100k$. Define the proportion of seats won by the Programmers after election $k$ to be $\hat{p}_k$.

The strategy will be to have the following inequality hold for each year.

$2\sqrt{100k}(\hat{p}_k-0.5) < 2.575$

Some algebra gives the solution to be as below.

$\hat{p}_k < \frac{0.12857}{\sqrt{k}} + 0.5$

Let $p_k$ be the probability for the coin in election $k$. Then, we can use the following formula to calculate the expected value of $\hat{p}_k$.

$\hat{p}_k = \frac{s+100p_k}{100k}$

Substituting for $\hat{p}_k$ into the previous inequality gives

$\frac{s+100p_k}{100k} < \frac{0.12857}{\sqrt{k}} + 0.5$,

and we can solve for $p_k$ to get

$p_k < 0.12875\sqrt{k} + 0.5k - \frac{s_k}{100}$.

For a comparison between the previous 100-year example. See the spreadsheet at the bottom of the post. You will see that the expected number of supermajorities is about 5.70 versus the 5.05 from the third part.

Part Five – A Piece of the Action

The last part asks if there is an advantage to the Programmers if they change the coin flips on a seat-by-seat basis. The answer appears to be no, but I must admit to being a bit shaky on my reasoning of why this is true.

When adding to binomial distributions with different probabilities of success, such as $\frac{1}{2}$ and $p_1 > \frac{1}{2}$, then the expected value of the sum would be the same as a binomial distribution with probability of success $\bar{p}$, the weighted average of the first two probabilities of success. As far as the Theorists are concerned, they can only see the proportions of wins, and the expected value is the most important part of the Programmers not getting caught.

However, the variance of the sum of the two binomial distributions would be smaller than the variance of one binomial distribution with probability of success $\bar{p}$. The problem with a smaller variance is that the probability of getting a number of wins above the mean would decrease. So, the probability of getting a supermajority would go down if the Programmers attempt to rig only certain seats.

Conclusion – The Only Winning Move is Not to Play

One important aspect not mentioned in the analysis above is what happens to the Programmers if they get unlucky. In Part 4, the programmers were pushing the limits of getting caught from one year to the next, there is only a 99% chance they do not get caught in any year. There is a 98% they do not get caught in the first two years, and a 97% chance they do not get caught in the first three years. In fact, the Programmers can only go 69 years before there is a less than 50% chance they will not get caught.