Two Plus Two Older Archives The Ballot Box
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#1
10-14-2002, 08:37 AM
 irchans Senior Member Join Date: Sep 2002 Posts: 157
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
#2
10-15-2002, 07:33 PM
 PseudoPserious Senior Member Join Date: Oct 2002 Posts: 151
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

#3
10-16-2002, 01:13 AM
 PseudoPserious Senior Member Join Date: Oct 2002 Posts: 151
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
#4
10-16-2002, 08:58 AM
 irchans Senior Member Join Date: Sep 2002 Posts: 157
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.

#5
10-16-2002, 09:52 AM
 PseudoPserious Senior Member Join Date: Oct 2002 Posts: 151
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
#6
10-16-2002, 04:45 PM
 irchans Senior Member Join Date: Sep 2002 Posts: 157
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.)
#7
10-16-2002, 07:10 PM
 PseudoPserious Senior Member Join Date: Oct 2002 Posts: 151
Re: The Ballot Box

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

PP
#8
10-17-2002, 07:24 AM
 irchans Senior Member Join Date: Sep 2002 Posts: 157

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)
#9
10-17-2002, 07:27 AM
 irchans Senior Member Join Date: Sep 2002 Posts: 157

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.

#10
10-20-2002, 08:00 PM
 PseudoPserious Senior Member Join Date: Oct 2002 Posts: 151

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

 Thread Tools Display Modes Linear Mode

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Two Plus Two     Two Plus Two Internet Magazine     About the Forums     MOD DISCUSSION     ISOP General Poker Discussion     Texas Hold'em     Beginners Questions     Books and Publications     Televised Poker     News, Views, and Gossip     Brick and Mortar     Home Poker     Poker Beats, Brags, and Variance     Poker Theory Limit Texas Hold'em     Mid- and High-Stakes Hold'em     Medium Stakes Hold'em     Small Stakes Hold'em     Micro-Limits     Mid-High Stakes Shorthanded     Small Stakes Shorthanded PL/NL Texas Hold'em     Mid-, High-Stakes Pot- and No-Limit Hold'em     Medium-Stakes Pot-, No-Limit Hold'em     Small Stakes Pot-, No-Limit Hold'em Tournament Poker     Multi-table Tournaments     One-table Tournaments Other Poker     Omaha/8     Omaha High     Stud     Other Poker Games General Gambling     Probability     Psychology     Sports Betting     Other Gambling Games     Rake Back     Computer Technical Help Internet Gambling     Internet Gambling     Internet Bonuses     Software 2+2 Communities     Other Other Topics Other Topics     Sporting Events     Politics     Science, Math, and Philosophy     The Stock Market

All times are GMT -4. The time now is 08:16 AM.