The probability of winning

You are the only sane voter in a state with candidates running for Senate. There are N other people in the state and each one votes completely randomly. All voters act independently and are equally likely to vote for either candidate (i.e., they choose their vote by a coin flip). What are the odds that your vote changes the outcome of the election? Specifically, how do these odds scale with the number of people in the state? You can keep your "state" population small... The answer should be apparent by 100,000. What is a simple function (i.e., b/N²) that describes the odds, where b is a constant? Can you find any special meaning for b?

This is what I have done I am not sure what they mean about drawing the graph and stuff.

>> P=1/n;

>> rand(P)

ans =

0.0975 0.9575 0.9706

0.2785 0.9649 0.9572

0.5469 0.1576 0.4854

Answer 1

[David Hill]

count=1;
odds=zeros(1,100);
for n=2:100:10000
 b=sym(((n/2+1):n)/4);
 c=sym(1:(n/2));
 a=prod(b./c);
 odds(count)=double(a/(1-a));
 count=count+1;
end
plot(2:100:10000,odds);

[Ntombikayise Bhengu]

Thank you so much.

Answer 2

[Walter Roberson]

What is a simple function (i.e., b/N²) that describes the odds, where b is a constant?

There is no such simple function.

First of all, you can only affect the election outcome this way when there are an equal number of other voters for each side, which requires that N be even. For example, if there are 5 other voters they might have voted 0:5, 1:4, 2:3, 3:2, 4:1, 5:0 and in none of those does your vote change the outcome of the election, unless you describe forcing a tie as changing the outcome (but the problem does not describe what happens when there is a tie.)

So given an even number N, the odds that you affect the election is the same as the odds that exactly N/2 people voted for each side. There is an analytic expression for that. The number of different ways in which exactly N/2 people voted for each side is Binomial(N, N/2) which is factorial(N)/factorial(N/2)/factorial(N/2) which is factorial(N)/factorial(N/2)^2 . There are 2^N ways in which a list of people can vote for two possibilities, so the odds that exactly N/2 will vote for each side becomes factorial(N)/factorial(N/2)^2/(2^N) .

factorial(N)/factorial(N/2)^2/(2^N) is not expressible in the form b/(N^2) .

You can test whether the formula is correct:

syms N
G(N) = factorial(N)/factorial(N/2)^2/(2^N);
n = 20;
sum(sum(dec2bin(0:2^n-1)-'0',2) == n/2)/2^n
double(G(n))

ans = 0.176197052001953

ans = 0.176197052001953

Exact match. Here, dec2bin()-'0' is doing the work of building all possible votes for n voters; sum across the second dimension gives the total number of votes for one side; we test whether that is exactly half of the voters, and we total the number of such occurrences and divide by the total number of possibilities in order to get the odds.

If, hypothetically, there were a b such that b were constant and b/N^2 were the odds, then if we were to take G(N)*N^2 for two different N, we would expect to see something approaching a constant. The question believes that the pattern should be settled by N = 100000 . So take double(G(N)*N^2) for 100000 and 200000 and if the question is right then you would expect to see something close to the same value. But you don't.

There is a relationship: the probability for P*N compared to the probability for N is 1/sqrt(P) times smaller as N approaches infinity.

[Ntombikayise Bhengu]

Thank you so much.

Answer 3

[Image Analyst]

For even more fun, why not run a Monte Carlo experiment to empirically determine the probability and then plot the probability as a function of N. By the way, what is n in your code? Is it supposed to be N? MATLAB is case sensitive you know.

% Initialization steps:
clc;    % Clear the command window.
close all;  % Close all figures (except those of imtool.)
clearvars;
workspace;  % Make sure the workspace panel is showing.
format short g;
format compact;
fontSize = 16;
markerSize = 15;

numberOfExperiments = 1000;
population = [4:2:100, 120 : 20 : 5000] % Number of other votes.  Don't go past 100,000
brokeTies = zeros(size(population));
for p = 1 : length(population)
	thisPopulation = population(p);
	fprintf('Running election with %d voters.\n', thisPopulation);
	% For this size population, run the random voting experiment 1000 times.
	numTies = 0;
	for k = 1 : numberOfExperiments
		votes = randi([0, 1], 1, thisPopulation); % 0 or 1 for all 100,000 voters.
		% Your vote will be the deciding vote if there are
		% the same number of 0's and 1';
		voted1 = nnz(votes);
		voted0 = thisPopulation - voted1;
		if voted0 == voted1
			% You're the deciding vote
			numTies = numTies + 1;
		end
	end
	% Convert to a percentage
	brokeTies(p) = numTies / numberOfExperiments;
end
plot(population, brokeTies, 'b.-', 'LineWidth', 2);
grid on;
title('Monte Carlo Simulation of Tie Breakers', 'FontSize', 20);
xlabel('Number of Voters', 'FontSize', 20);
ylabel('Probability you were the tie breaker', 'FontSize', 20);

[Ntombikayise Bhengu]

Thank you so much.