Enigma Election

The Riddler Classic 268, published 04/23/2021

From Aaron Wilkowski comes a rather enigmatic election:

Riddler Nation’s neighbor to the west, Enigmerica, is holding an election between two candidates, A and B. Assume every person in Enigmerica votes randomly and independently, and that the number of voters is very, very large. Moreover, due to health precautions, 20 percent of the population decides to vote early by mail.

On election night, the results of the 80 percent who voted on Election Day are reported out. Over the next several days, the remaining 20 percent of the votes are then tallied.

What is the probability that the candidate who had fewer votes tallied on election night ultimately wins the race?

The simulation

To simulate the election, I will produce 10,000 values from a binomial distribution with p = 0.5. I’ll look at whether the proportion of 1’s in the first 8,000 is greater than or equal to 0.5 and then determine whether the proportion of 1’s in all 1asw0,000 is the opposite.

Election <- function(N){ # N is the number of simulations
   otherCandidateWins <- 0
   for(i in 1:N){
      Elct <- rbinom(10000,1,0.5)
      A8 <- sum(Elct[1:8000])/8000
      All <- sum(Elct)/10000
      if((A8>0.5 & All <0.5) || (A8<0.5 & All>0.5)){
         otherCandidateWins <- otherCandidateWins + 1
      }
   }
   return(otherCandidateWins/N)
}

Now, let’s look at several simulations of 100000.

Election(10000)

## [1] 0.1386

If we have X represent the number of individuals favoring candidate A out of a population of 0.8N, and Y represent the number of individuals favoring candidate A out of a population of 0.2N, these are both binomial random variables. The X with paramers n=0.8N and p = 0.5, and the Y with parameters n=0.2N and p = 0.5. The same can be said for the numbers favoring candidate B, which are 0.8N-X and 0.2N-Y, respectively.

For large N, (X/(0.8N)) is approximately normal with mean 0.5 and variance 0.25/(0.8N), while (Y/(0.2N)) is approximately normal with mean 0.5 and variance (0.25)/(0.2N).

When $X-(0.8N-X) = 2X-0.8N > 0$, then out of the first 80%, candidate A was favored. We would then be interested in the probability that $((0.2N-Y)-Y) = 0.2N - Y > 2X - 0.8N$, or, the probability that the number favoring candidate B in the next 20% is greater than the previous number.

Analagously, we’re also interested in the event in which all the signs above are reversed. This, however, will be the same computation, so we will multiply are answer by two in the end.

Manipulating both sides, we get $0.2N-Y > 2X - 0.8N \rightarrow \frac{0.2N-Y}{0.2N}(0.2N) > \frac{2X-0.8N}{0.8N}(0.8N)$ which is the same thing as $\frac{0.2N-2Y}{0.2N} > 4\frac{2X-0.8N}{0.8N}$.

Using the random variable $W = (0.2N-2Y)/(0.2N)$ and $U = (2X-0.8N)/(0.8N)$, the probability density functions for these two are $f(w) = \frac{\sqrt{N}}{\sqrt{10\pi}}\exp\{-\frac{Nw^2}{10}\}$ and $f(u) = \frac{2\sqrt{N}}{\sqrt{10\pi}}\exp\{-\frac{4Nu^2}{10}\}$.

Our answer will be $\frac{2N}{10\pi}\int_0^\infty \int_{4u}^\infty \exp\{\frac{-(4u^2N+w^2N)}{10}\} dw\,dx$.

Using the pracma package in R will provide us a way to calculate double integrals. We calculate it below for N = 250. As the integrate2() function in the pracma package does not allow integrating to Inf, we use 100 instead.

N <- 250
integrand <- function(x,y){
   return(2*N/(10*pi)*exp(-(4*x^2*N+y^2*N)/10))
}
integral2(integrand,0,100,function(x) 4*x,100)$Q * 2

## [1] 0.147592

This provides a value very close to the simulated value. Using WolframAlpha, the exact answer can be expressed nicely as $\arctan(1/2)/\pi \approx 0.1475836$.