# Expected number of strikes to kill a $3$-headed dragon

You want to slay a dragon with $$3$$ heads. There is $$0.7$$ chance of destroying a head and $$0.3$$ chance of missing. If you miss, a new head will grow. $$X$$ is a random variable for the number of rounds until you slay all $$3$$ heads. Find $$E[X]$$.

I get the following pmf that $$P(X = n) = {?}\ 0.7^{k} 0.3^{k-3}$$ where $$n$$ is the number of slays ($$3$$, $$5$$, $$7$$...) and $$k$$ is the number of strikes that destroy a head. I am struggling with coming up with a coefficient for the expression or number of ways to permute successes and failures. I understand that the missing strikes cannot be at the end, and there also cannot be more than $$2$$ successful strikes before the 1st miss. How to think of a expression to capture the coefficient?

• I suggest working recrusively. Let $E_-$ denote the expected number of rounds until you lower the number of heads by $1$. Note that lowering the number of heads by $2$ is then expected to take $2E_-$ rounds and so on.
– lulu
Dec 1, 2023 at 12:36
• I think the coefficient is closely related to the Catalan numbers. The number of heads goes up and down like a Dyck-path and musn't go below level 1 and it starts at level 3 and ends on level 1 (the last slay then goes to level 0). Seem to be called Lobb numbers: en.wikipedia.org/wiki/Lobb_number So I'd say Lobb_{2, n-1}. Dec 1, 2023 at 13:30
• Continuation.. Their generating function will give the expectation as you put the 0.7 and 0.3 to the x part and sum. It surely has a some sort of squareroot as also here: books.google.fi/books?id=DmXmBwAAQBAJ on page 116 in talking about the infinite drunkards walk (which this problem is) there appears the $\frac{1-\sqrt{1-4pqu^2}}{2pu}$ (similar to Catalan generating function). Dec 1, 2023 at 13:50
• I hope it's okay that I replaced “slays” with “strikes”. In English “slay” usually means “kill’ and it is a verb, never a noun.
– MJD
Dec 1, 2023 at 14:09
• Yes, it's $\frac{i}{q-p}$! That squareroot thingy collapses into $q-p$. But if you want to calculate something more than the expected value, you have that Lobb generating function to do it. Dec 1, 2023 at 14:26

Let $$\epsilon_1,\ldots,$$ be iid random variables such that $$P(\epsilon_1=1) = 0.3$$ and $$P(\epsilon_1=-1) = 0.7$$.

Defining the random walk $$S_0=3$$, $$S_n = 3+\sum_{k=1}^n \epsilon_k$$, and the hitting time $$\tau$$ where $$S_{\tau}=0$$, you're looking for $$E[\tau]$$.

It is well-known that $$E[\tau] = \frac{3}{0.7-0.3}=7.5$$.

To expand on the discussion in the comments:

Let $$E_-$$ denote the expected number of rounds it takes to lower the number of heads by $$1$$. This is, of course, independent of the number of heads you are currently facing. It is also clear that the expected number of rounds needed to remove $$n$$ heads is just $$nE_-$$.

Considering the results of the next round we see that $$E_-=.7\times 1+.3\times (1+2E_-)=1+.6E_-\implies E_-=2.5$$

It follows that you expect it to take $$3E_-=7.5$$ rounds to slay the dragon.

• Can I ask if there is a way to get variance using the same method? So using this method to get E[X^2] somehow Dec 2, 2023 at 10:01
• You can, but it is messier. See this question for a discussion related to a similar problem (they have a symmetric process, but that's not a big change).
– lulu
Dec 2, 2023 at 11:22