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