What is the expected time to count to $x$, with two people, $1/2$ chance player 1 counts a step, $1/2$ chance player 2 counts a step

Question

So we have two people, starting at 0. At each time step, we randomly select one of the two people ($1/2$ chance of picking each), and they increase their count by one. We look for the expected time until someone reaches some selected number $x$.

I can solve this problem quite easily: $E_{0,0} = 1 + 1/2 E_{0,1} + 1/2 E_{1,0}$, etc. etc. But this is actually quite a bit of working out for a problem which seems so simple. Is there a quick, intuitive way of solving this?

Answer 1

You don't have to derive a formula from scratch. OEIS A033504:

$a(n)/4^n$ is the expected number of tosses of a coin required to obtain $n+1$ heads or $n+1$ tails.

A formula for $a(n)$ is helpfully given there by Vladeta Jovovic: $$a(n)=(n+1)\left(2^{2n+1}-\binom{2n+1}{n+1}\right)$$ Adapting it to the problem at hand, where $x=n+1$, we have $$E(x)=\frac{x\left(2^{2x-1}-\binom{2x-1}{x}\right)}{4^{x-1}}$$