 Two Plus Two Older Archives (http://archives2.twoplustwo.com/index.php)
-   Probability (http://archives2.twoplustwo.com/forumdisplay.php?f=23)
-   -   The Ballot Box (http://archives2.twoplustwo.com/showthread.php?t=22042)

 irchans 10-14-2002 08:37 AM

The Ballot Box

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

Re: The Ballot Box

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

Re: The Ballot Box

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

Re: The Ballot Box

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.)

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
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

Re: The Ballot Box

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

Re: The Ballot Box

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

Re: The Ballot Box

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)

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