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$?


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.