PDA

View Full Version : The Ballot Box

irchans
10-14-2002, 08:37 AM
I read the following related questions in a probability book. I need the binomial theorem to solve #2, but I keep thinking there is a simpler solution.

#1 "In an election, two candidates, Albert and Benjamin, have in a ballot box a and b votes respectively, a&gt; b, for example, 3 and 2. If ballots are randomly drawn and tallied, what is the chance that at least once after the first tally the candidates have the same number of tallies?"

#2 "Players A and B match pennies N times. They keep a tally of their gains and losses. After the first toss, what is the chance that at no time during the game will they be even?"

From "Fifty Challenging Problems in Probability" by Frederick Mosteller

PseudoPserious
10-15-2002, 07:33 PM
Nice problems, irchans. Are you looking for a closed form solution? I think I have an iterative answer for each -- but I'm sure you'll disabuse me of that notion in short order.

#1. Let's call the probability of being tied for the first time when you tally the Nth vote P(N). If we can calculate all of the P(i) for i=1 to 2b, then we can sum the P(i)'s to get the probability of tieing at least once. (Note: if you haven't tied by the time you've counted 2b votes, then you won't tie...you have more a votes tallied then there are b votes available.)

I think that this makes sense:
P(N) = (probability of not having a tie with votes 1 through (N-1))*(probability of drawing N/2 a votes and N/2 b votes in N tries from the population (a+b) without replacement)
The second term calculates the odds of being tied on the Nth draw. The first term reduces those odds so we don't double count the permutations of a's and b's that would have tied on earlier draws. Let's use this notation:

P(N)=(1-Sum[P(i),i=1...(N-1)])*P(x)

For any odd N, P(x)=0 since you can't get a tie on an odd number of votes.

For any even N, P(x)=C(a,x)C(b,x)/C(a+b,2x), where x=N/2. This is the hypergeometric distribution. P(x) represents the odds of choosing x a's and x b's on 2x draws from a total population of (a+b).

Using these formulas, given a and b you can calculate all the P(i)'s and add them up.

#2. I'm not familiar with 'matching pennies', but I'll assume that there's a 50% chance of A gaining a point and 50% chance of B gaining a point. Using a similiar thought process, the probability of being tied for the first time on the nth toss is:

P(n)=(1-Sum[P(i),i=1...(n-1)])*P(x)

Again, P(x)=0 for odd n.

For even n, we have P(x)=C(n,x)(.5)^n, where x=n/2. This is the binomial distribution.

So we sum up all of the P(n) for n=1 to N and voila.

Is this anywhere near coherent, irchans? It's been a long day and my brain is pretty fried.

PP

PseudoPserious
10-16-2002, 01:13 AM
Okay, I thought about this some more on the drive home...I no longer think that:

P(N) = (probability of not having a tie with votes 1 through (N-1))*(probability of drawing N/2 a votes and N/2 b votes in N tries from the population (a+b) without replacement)

makes sense. I think I'm still double counting somewhere. I'll think about it some more tomorrow.

PP

irchans
10-16-2002, 08:58 AM
Pseudo,

I entered your formulas into my computer. They gave an excellent approximation to the exact probability. For small a and b, it is not too hard to get the exact probability by enumerating all the possibilities. For example, if a=3 and b=2, there are only 10 possible sequences of votes:

AAABB, AABAB,
AABBA, ABAAB, ABABA, ABBAA,
BAAAB, BAABA, BABAA, BBAAA.

Notice that 8 of the 10 possibilities have a tie so the probability is 8/10 = 4/5. (AABBA and BBAAA tie after the 4th vote, the other 6 tie after 2 votes.)

Your formulas are good approximations because your equation

P(N) = (probability of not having a tie with votes 1 through (N-1))*(probability of drawing N/2 a votes and N/2 b votes in N tries from the population (a+b) without replacement)

assumes that those two probabilities are independent which is often true. I used your formulas and tedious enumeration to generate probabilities and got the following results:

<pre><font class="small">code:</font><hr>
probability
a b pseudo answer
formulas by enumerating
all possibilities

1 0 0 0
1 1 1 1
2 0 0 0
2 1 2/3 2/3
2 2 1 1
3 0 0 0
3 1 1/2 1/2
3 2 21/25 4/5
3 3 1 1
4 0 0 0
4 1 2/5 2/5
4 2 18/25 2/3
4 3 1562/1715 6/7
4 4 1 1
</pre><hr>

The formulas were either exactly correct or off by just a little bit in every case.

PseudoPserious
10-16-2002, 09:52 AM
Hey irchans,

After a decent night's sleep and a half hour commute, I think I realized what I did wrong -- I think the idea was good, I just didn't implement it correctly. Here goes:

Call P(n) the probability of being tied for the first time on the nth draw. Call p(n) the probability of being tied on the nth draw. Then:

P(n)=Product[(1-p(i)),(i=1 to (n-1))]*p(n)

This looks like a straight application of conditional probability (a probability 'tree'), so it should handle properly handle independence.

Then by using:

p(x)=C(a,x/2)C(b,x/2)/C(a+b,x), or
p(x)=C(x,x/2)(.5)^x

for the first and second cases respectively, you can sum up all of the P(n) to get the probability.

Better?
PP

irchans
10-16-2002, 04:45 PM
Pseudo, I tried your new formulas and I got the following answers for a = 3 votes and b = 2 votes.

Counting:
AAABB, AABAB,
AABBA, ABAAB, ABABA, ABBAA,
BAAAB, BAABA, BABAA, BBAAA.

8 ties out of 10 = 4/5.

Formulas:
p(odd)=0
p(2) =3/5
p(4) =3/5
P(2) =3/5
P(4) =2/5*3/5 = 6/25
chance of tie at any point = P(2)+P(4)= 6/25+ 3/5 = 21/25

21/25 is close, but not perfect. (The new formulas were often correct and always close in every example I tried.)

PseudoPserious
10-16-2002, 07:10 PM
You're right, that doesn't handle the dependence. Grrrr. What did you get?

PP

irchans
10-17-2002, 07:24 AM
I got 2 b / (a + b) after I did a ridiculous amount of work.
Then I read a simple the simple solution below.

solution :

If the first vote is B, then there will be a tie.

b/ (a + b) = P(first vote is B)
= P(first vote is B and a tie occurs)

Suppose you have a voting sequence that has a tie and the first vote is not B. Switch all the A's and the B's up to the tie vote, then you get a voting sequence with the same number of A's and B's starting with a B. So,

P( first vote is A and a tie occurs ) =
P( first vote is B and a tie occurs ) = b/ (a + b)

Adding them together we get

P(tie occurring) = 2 b / (a + b)

irchans
10-17-2002, 07:27 AM
I have never seen a "simple" solution to the penny matching. The best solution I have seen for penny matching requires the binomial expansion of (a+b)^n and a page of algebra.

PseudoPserious
10-20-2002, 08:00 PM
Hmmm, neat solution to the ballot box. Do you buy that reasoning for the simple problem? It gives the right answer, but it doesn't feel right to me...of course, I've thought about it for all of 10 seconds or so.

PP

irchans
10-21-2002, 05:42 AM
&gt;Do you buy that reasoning for the simple problem?

Yup. Mainly I find the simple reasoning convincing because I can see how it could be changed into a formal proof, but I also love the simplicity of solutions like that.

Cheers, Irchans.