9
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$
    – lulu
    Dec 1, 2023 at 12:36
  • $\begingroup$ 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}. $\endgroup$
    – ploosu2
    Dec 1, 2023 at 13:30
  • $\begingroup$ 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). $\endgroup$
    – ploosu2
    Dec 1, 2023 at 13:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – MJD
    Dec 1, 2023 at 14:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – ploosu2
    Dec 1, 2023 at 14:26

2 Answers 2

9
$\begingroup$

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$.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – clement
    Dec 2, 2023 at 10:01
  • $\begingroup$ 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). $\endgroup$
    – lulu
    Dec 2, 2023 at 11:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .