Two Plus Two Older Archives  

Go Back   Two Plus Two Older Archives > General Gambling > Probability

Reply
 
Thread Tools Display Modes
  #1  
Old 10-14-2002, 08:37 AM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default 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> 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
Reply With Quote
  #2  
Old 10-15-2002, 07:33 PM
PseudoPserious PseudoPserious is offline
Senior Member
 
Join Date: Oct 2002
Posts: 151
Default 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


Reply With Quote
  #3  
Old 10-16-2002, 01:13 AM
PseudoPserious PseudoPserious is offline
Senior Member
 
Join Date: Oct 2002
Posts: 151
Default Re: The Ballot Box

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
Reply With Quote
  #4  
Old 10-16-2002, 08:58 AM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default 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.)


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.

Reply With Quote
  #5  
Old 10-16-2002, 09:52 AM
PseudoPserious PseudoPserious is offline
Senior Member
 
Join Date: Oct 2002
Posts: 151
Default 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
Reply With Quote
  #6  
Old 10-16-2002, 04:45 PM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default Re: The Ballot Box

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.)
Reply With Quote
  #7  
Old 10-16-2002, 07:10 PM
PseudoPserious PseudoPserious is offline
Senior Member
 
Join Date: Oct 2002
Posts: 151
Default Re: The Ballot Box

You're right, that doesn't handle the dependence. Grrrr. What did you get?

PP
Reply With Quote
  #8  
Old 10-17-2002, 07:24 AM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default Answer to Ballot Box

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)
Reply With Quote
  #9  
Old 10-17-2002, 07:27 AM
irchans irchans is offline
Senior Member
 
Join Date: Sep 2002
Posts: 157
Default Re: Answer to Ballot Box

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.

Reply With Quote
  #10  
Old 10-20-2002, 08:00 PM
PseudoPserious PseudoPserious is offline
Senior Member
 
Join Date: Oct 2002
Posts: 151
Default Re: Answer to Ballot Box

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
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -4. The time now is 09:57 AM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.