My friend posed a question a couple of days back which states the following. There is a dragon which starts with 3 heads, and we can cut one head at a time. Everytime we cut one head, either nothing happens, two heads grow back or three heads grow back. We are asked to find the probability of cutting off all heads.
So I modelled this as a random walk on $\mathbb Z$ with an absorbing barrier at $x=0$. We either go back one step, go forward one step or go forwards two steps, each with equal probability. Let us take $P_k$ to be the probability of starting at $x=k$ and hitting $x=0$ eventually. We then need to find $P_3$. The recursion I am looking at is $$3P_k=P_{k-2}+P_{k-1}+P_{k+1}$$ with the obvious boundary condition $P_0=1$. The solution to this recurrence is $$P_k=A+B(1-\sqrt2)^k+C(1+\sqrt2)^k$$ with $A+B+C=1$. I want my probabilities to be bounded, so $C$ must be $0$.
But here I am stuck. I would need one more boundary condition to proceed, which I am not sure what it might be. I am trying to look at the fact that the mean motion is $2/3$ steps to the right and hence the probability of eventually getting absorbed must decrease (and hence $A=0$? But then the probabilites are negative at odd values of $k$).
I am at a loss how to proceed, or maybe I have done something wrong. Any help is appreciated.
I think you have the recurrence slightly wrong and it should be $P_k= \frac13 P_{k-1}+\frac13P_{k+1}+ \frac13 P_{k+2}$ for $k > 0$ i.e. $$3P_k=P_{k-1}+P_{k+1}+ P_{k+2}$$
You are missing the key observation that $P_0=1$, $P_2=P_1^2$, and in general $P_k=P^k_1$. You want all of any descendents of each the $k$ heads to eventually die out.
So you want to solve $x^3+x^2-3x+1=0$ to find $P_1$, which has the roots $1$, $-\sqrt{2}-1$ and $\sqrt{2}-1$. The first two of those are implausible (the probability is positive, but there is also a positive probability the number of heads will explode), so $P_1=\sqrt{2}-1\approx 0.414$.
Since the dragon starts with $3$ heads, you actually want $P_3=P_1^3 = \sqrt{50}-7\approx 0.071$.