aez-notes

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?

Note that matching pennies appears to just calling heads and tail multiple times.

Consider the case where A wins \(x\) of the flips, then the probability that they have an even number of wins at some point can be calculated using the result from the Ballot Box problem:

\[ \frac{2\min\{x,N-x\}}{N} \]

Since the distribution of \(x\) is known to follow a binomial distribution in this problem we can use the law of total expectation to compute the probability that there is an equal number of wins at some point.

\[ \sum_{x=0}^{N} \frac{2\min\{x,N-x\}}{N} \binom{N}{x} 2^{-N} \]

which we can decompose into the following into the first \(a\) terms, a single term and the remaining terms, where \(a\) is either the middle term or one off of it. This being decided so as to ensure that the probability of a pair is never greater than one.

\[ \sum_{x=0}^{a-1} \frac{2x}{N} \binom{N}{x} 2^{-N} + \frac{2a}{N} \binom{N}{a} 2^{-N} + \sum_{x=a+1}^{N} \frac{2(N-x)}{N} \binom{N}{x} 2^{-N} \]

We can then observe that over the values we are considering \(\binom{N}{x}\) is equal to \(\binom{N}{N-x}\) so the second sum can be expressed as the following.

\[ \sum_{x=a+1}^{N} \frac{2(N-x)}{N} \binom{N}{N-x} 2^{-N} \]

In each sum we can then take the numerator and denominator into the binomial coefficient and cancel one factor of 2 and the resulting expressions look like the values of the binomial distribution with \(N-1\) trials. There is a left over term, but it is equal to zero anyway.

So the final probability of there being no tie at any point is the complement of this,

\[ \frac{2a}{N} \binom{N}{a} 2^{-N}. \]

If \(N\) is even, then \(N = 2n\) then \(a=n\) and this simplifies to \(\binom{N}{n}2^{-N}\) and if it is odd, then \(N = 2n + 1\) and \(a=n+1\) and it simplifies to \(\binom{N-1}{a-1}2^{-N-1}\), which after replacing \(a\) with \(n+1\) is \(\binom{N-1}{n}2^{-N}\).