[PseudoPserious]

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