'We have a fair coin. I gain one on a head. I lose one on a tail. I quit when my position is +1. What's the probability that the game terminates? What's my expected winnings when the game ends?'
I am struggling to find the probability that the game ends, which I think I am correct in saying is also equal to the expected winnings. I know that to win, we need to have $ k+1$ heads and $k$ tails for some $k\in\{0,1,2,\ldots\}$ subject to the condition that before we get the $(k+1)$th head the number of heads can never exceed the number of tails. This makes counting the possibilities tricky. I also tried drawing a tree diagram and attempting to construct some linear equation in $p$ (the probability the game ends), but again because of the constraint I couldn't get far with this. I also tried to think of it as a symmetric random walk, but because we only have one initial condition I cannot solve the recurrence to find $p_0$.
Can I have a hint on how to solve this problem?