Think of this problem instead as a random walk along the number line, starting at zero. If the walker ever returns to zero, then success is achieved. Let xi be the probability of success from point i on the number line. Let p be the probability that the walker moves to the right. Let's also let p be the lesser of the probabilities of flipping heads and tails.
I hope I won't have to prove that x-1=1. In other words, the gravity of the greater probability of q will pull the walker to the right, over the long run. So if his first move is to the left, he will eventually make it back to point 0. For the same reason, given a casino game with a house advantage, the house always wins in the long run. If the player wins his first bet, if he plays indefinitely, he will eventually lose it back.
That said, we can set up the following equations:
x0 = p + q×x1
x1 = p + q×x2
x2 = p×x1 + q×x3
x3 = p×x2 + q×x4
.
.
.
Next, take the sum of both sides.
Let E = x0 + x1 + x2 + ...
E = 2p + pE -p×x0 + qE - q×x0
E = 2p + E×(p+q) - x0×(p+q)
E = 2p + E - x0 (because p+q=1)
0 = 2p - x0
x0 = 2p
So the answer is 2p.
Below are the results of computer trials which have verified the answer above. For each probability p 100,000 trials were conducted, in which a trial ended when either the number of heads equalled the number of tails, or the difference was more than 25. It seems reasonable to assume that for p<=.4 if the difference ever equals 25 it is very unlikely that the gap ever be closed. A 'win' means the number of heads was ever equal to the number of tails. The number of losses would be 100,000 minus the number of wins.
p wins ----- ------ 0.4 80058 0.3 59799 0.2 39957 0.1 19803
If you don't buy my solution, I have posted altnernate solutions by Richard Tucker and David Beim.
Thanks to Guy de Kindler for providing the problem and Richard Tucker and David Beim for the alternate solutions.
Michael Shackleford, A.S.A.