Expected value for number of ties in n coin tosses?

Question

I flip a coin $n$ times, at each toss I count how many heads and how many tails have come out so far.

An example with $n=4$ might be:

 Heads Tails 
   1     0   
   1     1   (here I count 1 tie so far) 
   2     1   
   2     2   (and here I count a total of 2 ties) 

In this run, I get 2 ties total.

Now my question is, assuming I flip the coin an even number of times, what is the expected value for the amount of ties total after $n$ coin tosses, in terms of $n$?

Answer 1

We are tossing an even number $n$ of times. Let $n=2m$.

For $i=1$ to $m$, define the indicator random variable $X_i$ by $X_i=1$ if there is a tie after $2i$ tosses, and $X_i=0$ otherwise. Then the random variable $Y$ that counts the number of ties is given by $Y=X_1+\cdots +X_m$.

By the linearity of expectation we have $E(Y)=\sum_{i=1}^m E(X_i)$.

The expectation of $X_i$ is the probability that $X_i=1$, which is $\binom{2i}{i}\frac{1}{2^{2i}}$. So the required expectation is $$\sum_{i=1}^m \binom{2i}{i}\frac{1}{2^{2i}}.$$

This sum has a closed form whose correctness can be proved by induction. It is $$\frac{m+1}{2^{2m+1}}\binom{2m+2}{m+1}-1.$$

Answer 2

I may be wrong, but to me that seems very cumbersome to solve analytically, because the chance to have a tie after a specific number of flips depends on the outcomes of all previous flips (and hence the chance to get a tie after e.g. 10 flips is not independent of the number of ties you got before). I would try Monte Carlo simulation to get an estimate of the expected value - there may be better ways, though.