Here's the problem statement: "You are trying to save a princess from a dragon who starts with three heads. At each turn, you can either cut off one head, two heads, or no heads; regardless, the dragon will grow back one head unless all of its heads are cut off. For each turn, all outcomes are equally likely. What is the probability you defeat the dragon?"
Let's assume there's no cap on the number of heads the dragon can grow. In that case, we can write down recurrences $$P_3 = P_4/3 + P_3/3 + P_2/3$$
$$P_2 = P_3/3 + P_2/3 + 1/3$$
and many more for $P_4$, $P_5$, etc., where $P_i$ is the probability of defeating the dragon given that there are $i$ heads remaining. I'm struggling to find a way of solving this infinite system of equations, or seeing some kind of symmetry that makes $P_4$ easily expressable in terms of other probabilities. Any suggestions?
Probability of defeating a hydra that grows back its heads
probabilityrecursion
Best Answer
Think of it as a random walk: you start at $x=3$, then add a head, remove a head, or stay in the same place with equal probabilities. For simplicity, you can disregard all steps where you stay in the place and think about it as a random walk with equal probabilities to go right and left.
Here comes the punch: A symmetric random walk visits all points with probability 1, so sooner or later, w.p. 1, you will cut all the heads.