Probability that a coin flipping game ends in finite time Inspired by this video, consider the following setup. Alan starts with 0 points, and Nancy starts with 4. Alan then flips a coin. If it's heads, Alan gets 2 points and Nancy gets 1 point. If it's tails, Nancy gets no points and Alan loses all his points. Alan can keep flipping as long as he wants, and he wins if his score is ever equal to Nancy's score. What's the probability that Alan wins the game in a finite number of turns?
The first thing to notice is that any tails flipped at the start or after another tails don't change anything. We can use this to bound $P$. The lower bound is $P > 1/8$, since that's the probability Alan wins after flipping his first heads. We can get an upper bound by assuming that all of Alan's failures are the best-case scenario of only a single heads. Each subsequent string of heads is half as likely to succeed, so adding that all up gives $P < 1/4$. Thus we get a loose bound of $1/8 < P < 1/4$.
Narrowing those bounds, or finding P exactly, is something I'm having trouble with. This seems to be a Markov chain problem, but I don't know very much about those. Any help?
 A: Here is a way to compute $P$ to arbitrary precision, though I don't see how to get a closed form just yet.
Let $P(k)$ be the probability that Alan wins, starting from a state where Alan has $0$ points and Nancy has $k$ points.
From this state, let's have Alan flip the coin until it first lands heads, and then keep flipping the coin until it lands tails again or until Alan wins. The result is:

*

*With probability $1/2$ (assuming $k>1$) the first heads is followed by tails, and we end up with Alan at $0$ points again, and Nancy at $k+1$.

*With probability $1/4$ (assuming $k>2$) the first heads is followed by heads and then tails, and we end up with Alan at $0$ points again, and Nancy at $k+2$.

*In general, for every $1 \le i \le k-1$, with probability $1/2^i$, there is a run of $i$ heads followed by tails, and we end up with Alan at $0$ points again, and Nancy at $k+i$.

*Finally, there is a $1/2^{k-1}$ chance that there is a run of $k$ heads, in which case we stop flipping and Alan wins.

This gives us the recurrence
$$
   P(k) = \frac1{2^{k-1}} + \sum_{i=1}^{k-1} \frac1{2^i} P(k+i).
$$
That's the algebra; next is the numerical estimate.
We can repeatedly expand $P(4)$ by applying this recurrence to the first $P(k)$ term remaining:
\begin{align}
P(4) &= \frac{P(5)}{2}+\frac{P(6)}{4}+\frac{P(7)}{8}+\frac{1}{8} \\
   &=\frac{P(6)}{2}+\frac{P(7)}{4}+\frac{P(8)}{16}+\frac{P(9)}{32}+\frac{5}{32} \\
   &= \frac{P(7)}{2}+\frac{3 P(8)}{16}+\frac{3 P(9)}{32}+\frac{P(10)}{32}+\frac{P(11)}{64}+\frac{11}{64} \\
   &= \cdots
\end{align}
At each stage, we can get a lower bound for $P(4)$ by replacing all remaining $P(k)$ terms with $0$. Also, by the same argument that gives $P(4) < 1/4$ in the question, we have $P(k) < 1/2^{k-2}$, and replacing all remaining $P(k)$ terms with $1/2^{k-2}$ gives us an upper bound at each stage.
It turns out that if we go for a hundred steps or so, the lower and upper bound get pretty close together, and we get
$$
   P(4) \approx 0.18645370013265963349\dots
$$
We can get any number of guaranteed-correct digits in this way.
In a similar way, we can find $P(2) \approx 0.68331582634729417978\dots$. Since $P(1)=1$ (eventually the coin lands heads and Alan wins) the first nontrivial case is $P(2)$, so if we were looking around for closed forms, this would be the simplest value to start with. But I haven't found any reasonable conjecture for a closed form of either $P(2)$ or $P(4)$.
Experimentally, the following seems true. Let $c(k)$ be the coefficient of $P(k)$ at the step where we're about to apply the recurrence to $P(k)$, in our solution for $P(4)$. Then $c(k) = \frac{a(k-3)}{2^{k-4}}$ where $a(n)$ is the $n^{\text{th}}$ term of OEIS sequence A155099. (I have checked this for the first $26$ terms, which is how many OEIS has.) Since $P(k)$ contributes a constant term of $\frac1{2^{k-1}}$ when we apply the recurrence relation, $c(k)P(k)$ contributes $\frac{c(k)}{2^{k-1}}$, and we have
$$
    P(4) = \sum_{k=4}^\infty \frac{c(k)}{2^{k-1}} = \sum_{k=4}^\infty \frac{a(k-3)}{2^{2k-5}} = \sum_{n=1}^\infty \frac{a(n)}{2^{2n+1}}.
$$
OEIS sequence A155099 is the third column of A155092, so its other columns can probably be used to find sums like this for other values of $P(k)$, and maybe this can be used to go further.
