Riddler Classic – 11-4-2016 – Will You Decide the Election?

Here’s my solution to this week’s Riddler Classic puzzle FiveThirtyEight.  Here’s the question: ” You are the only sane voter in a state with two candidates running for Senate. There are N other people in the state, and each of them votes completely randomly! Those voters all act independently and have a 50-50 chance of voting for either candidate. What are the odds that your vote changes the outcome of the election toward your preferred candidate?  More importantly, how do these odds scale with the number of people in the state? For example, if twice as many people lived in the state, how much would your chances of swinging the election change?”

As with my previous solutions, I chose the simulation route with this one.  There are lots of other ways but this is the direction that interests me most.  Lets to a simulation and see how many times we get a tie, which is where a single vote would change the election.

The inner for loop represents a single trial where you iterate through all the voters and assign them a random number from 0 to 1.  One number represents candidate A and the other candidate B.  After iterating through all the voters you check and see if it was a tie.  If it was, you increase the tie counter.  We iterate from 0 to numPeople-1 to account for the face that you will also vote.

The middle for loop represents the number of trials for a given number of voters.  In my simulation I do 10000 trials.  Increasing the number of trials increases the accuracy but it’s a dimenishing return.

The outer for loop represents the number of people in the state.  Each time we triple the number of people and do the whole thing again.  Why triple?  Because it’s an easy way to make sure the number of voters is odd.

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int a;	// representing votes for candidate a
	int b;  // and candidate b
	int tied=0;	// represents number of trials where there was a tie
	const int NUM_TRIALS = 10000;	// number of trials - increase for more accuracy
	int x;
	double percentage;

	// We will
	for(int numPeople=3; numPeople<5000000; numPeople*=3)
	{
		tied=0; // reset tied counter

		// Conduct NUM_TRIALS number of simulations
		for(int trials=0; trials<NUM_TRIALS; trials++)
		{
			a=0;	// reset vote counts
			b=0;

			// Iterate through each person in the state until we read numPeople
			for(int person=0; person<numPeople-1; person++)
			{
				// Generate a random number, either 0 or 1
				// 0 represents candidate b, 1 represents candidate a
				x = rand()%2;
				if(x == 1)
					a++;
				else
					b++;
			}

			// If they are tied, increase the tied counter
			if(a==b)
				tied++;
		}

		// Calculate the percentage and print,
		//  using fflush after each time ensures it prints immediately instead of waiting
		percentage = 100.0 * tied / NUM_TRIALS;
		printf("%d people, %d trials, %d ties, %5f percentage chance of a tie\n", numPeople, NUM_TRIALS, tied, percentage);
		fflush(stdout);
	}
}

Doing this we get the following table and graph:

As you can see the chances that you decide the election are reduced drastically.  Also note that these numbers are slightly off from what we expect.  You would expect the chance at three people to be exactly 50% but instead we have 49.22%.  With simulations like this you will never be exact as you would with a mathematically formula, but the idea is that you throw enough iterations at it that it doesn’t really matter.

But this was just what would happen with two candidates.  What if there were three, or four, or five.  I’ve altered the section of code inside the inner most for loop and rerun the simulation for three, four, and five candidates.  I’ve also moved the checking for a tie portion to a function to make it more clear as things get complicated.  What I decided was that you only decide the election if there is a tie for the top two vote getters or the second place is one vote below the first place.  So I put the votes into an array and sorted them lowest to highest; this makes it so much easier to check.  You can see the code for the five candidate situation below.  Remember that we are assuming that other voters will randomly chose a candidate.

#include <stdio.h>
#include <stdlib.h>

int isTied(int a, int b, int c, int d, int e)
{
	int votes[5];
	int temp;
	votes[0] = a;
	votes[1] = b;
	votes[2] = c;
	votes[3] = d;
	votes[4] = e;

	// Sorts the array with the highest votes at position 4 and lowest at position 0
	for(int i=0; i<5; i++)
	{
		for(int j=0; j<4; j++) 		{ 			if(votes[j] > votes[j+1])
			{
				temp = votes[j];
				votes[j] = votes[j+1];
				votes[j+1] = temp;
			}
		}
	}

	// The two times you vote would change the outome of the election
	//  are if there is a tie at the top or if the second place is within
	//  one vote of the top which would force a tie and a revote.
	if(votes[4]==votes[3] || votes[3]+1==votes[4])
	{
		return 1;
	}
	else
	{
		return 0;
	}

}

int main()
{
	int a;	// representing votes for candidate a
	int b;  // and candidate b
	int c;
	int d;
	int e;
	int tied=0;	// represents number of trials where there was a tie
	const int NUM_TRIALS = 10000;	// number of trials - increase for more accuracy
	int x;
	double percentage;

	// We will
	for(int numPeople=5; numPeople<5000000; numPeople*=3)
	{
		tied=0; // reset tied counter

		// Conduct NUM_TRIALS number of simulations
		for(int trials=0; trials<NUM_TRIALS; trials++)
		{
			a=0;	// reset vote counts
			b=0;
			c=0;
			d=0;
			e=0;

			// Iterate through each person in the state until we read numPeople
			for(int person=0; person<numPeople-1; person++)
			{
				// Generate a random number, either 0 or 1
				// 0 represents candidate b, 1 represents candidate a
				x = rand()%5;
				if(x == 0)
					a++;
				else if(x == 1)
					b++;
				else if(x == 2)
					c++;
				else if(x == 3)
					d++;
				else if(x == 4)
					e++;

			}

			// If they are tied, increase the tied counter
			if(isTied(a,b,c,d,e) == 1)
				tied++;
		}

		// Calculate the percentage and print,
		//  using fflush after each time ensures it prints immediately instead of waiting
		percentage = 100.0 * tied / NUM_TRIALS;
		printf("%d people, %d trials, %d ties, %5f percentage chance of a tie\n", numPeople, NUM_TRIALS, tied, percentage);
		fflush(stdout);
	}
}

As you can see, you’ve got some weirdness happening at the very beginning but then it become clear that the more candidates you have, the better the chance that you decide the election.

As always, there’s a decent chance I did something wrong so if you see something, let me know in the comments below!