In this instance, I (think I) understand the logic behind the answer but seem to be falling down on the algebra.
The question is: A biased coin is tossed repeatedly. Find the probability that there is a run of r heads in a row before there is a run of s tails, where $r$ and $s$ are positive integers.
The answer is:
Let:
A = run of r heads precedes run of s tails
B = first toss is a head
C = first s tosses are tails
p = heads on a single toss
q = (1-p) is the probability of tails on a single toss
Then
$\begin{align}\mathbb{P}(A | B^c \cap C) &= (A | B^c \cap C)\mathbb{P}(C|B^c) + (A | B^c \cap C^c)\mathbb{P}(C^c|B^c)\\
&= 0 + \mathbb{P}(A|B)(1-q^{s-1})\end{align}$
Clearly, the first term on the left-hand side is zero as A and C can't both be true.
For the second term, we have a tail-first but the first $s$ tosses are not all tails so the process must reset and you now have the probability of r tosses in a row given that you re-started with a head. This is multiplied by the probability of not getting $s$ tails in a row.
$\mathbb{P}(A | B) = p^{r-1} + \mathbb{P}(A | B^c)(1-p^{r-1})$
Similar to the above we the first term corresponds to having $r-1$ heads after your first one.
The second term corresponds to the case where you don't get $r-1$ heads in a row and so the process "resets" and you have the probability of $r$ heads in a row given that you re-started with a tail. This is multiplied by the probability of not getting $r$ heads in a row.
Have I interpreted the answer correctly so far?
The answer then says use the fact that:
$\mathbb{P}(A) = \mathbb{P}(A |B)(p) + \mathbb{P}(A |B^c)(q)$
to obtain:
$\mathbb{P}(A) = \frac{p^{r-1}(1-q^s)}{p^{r-1}+ q^{s-1}-p^{r-1}q^{s-1}}$
I just can't seem to get the algebra to work!
Starting with:
$\begin{align} \mathbb{P}(A) &= \mathbb{P}(A |B)(p) + \mathbb{P}(A |B^c)(q) \\
&= [p^{r-1} + \mathbb{P}(A | B^c)(1-p^{r-1})]p + [\mathbb{P}(A|B)(1-q^{s-1})]q \\
& = [p^{r-1} + \mathbb{P}(A|B)(1-q^{s-1})(1-p^{r-1})]p + [\mathbb{P}(A|B)(1-q^{s-1})]q \\
& = [p^{r-1} + \mathbb{P}(A|B)(1 – q^{s-1} – p^{r-1} + q^{s-1}p^{r-1} )]p + [\mathbb{P}(A|B)(1-q^{s-1})]q \\
&= [p^{r-1} + \mathbb{P}(A|B)(- q^{s-1} – p^{r-1} + q^{s-1}p^{r-1} )]p + \mathbb{P}(A|B) \end{align} $
This is as far as I can get!
Can someone please help with the algebra?
Thanks
Best Answer
Personally I would approach this with something like
$$\mathbb P(A) = \mathbb P(A\mid B)\mathbb P(B) + \mathbb P(A\mid B^c)\mathbb P(B^c) \\= \mathbb P(A\mid B)p + \mathbb P(A\mid B^c)q\,\,\quad$$
where $$\mathbb P(A\mid B) = p^{r-1} +(1-p^{r-1})\mathbb P(A\mid B^c)$$ $$\mathbb P(A^c\mid B^c) = q^{s-1} +(1-q^{s-1})\mathbb P(A^c\mid B)\,\,\,\,$$
and since $\mathbb P(A^c\mid B^c) = 1- \mathbb P(A\mid B^c)$ and $\mathbb P(A^c\mid B) = 1- \mathbb P(A\mid B)$, these amount to two equations with two unknowns leading to $$\mathbb P(A\mid B^c) = (1-q^{s-1})\mathbb P(A\mid B)\,\,\qquad$$ $$\mathbb P(A\mid B) = \dfrac{p^{r-1}}{p^{r-1}+q^{s-1} - p^{r-1}q^{s-1}}$$ and finally substituting into the original equation and tidying the numerator $$\mathbb P(A) = \dfrac{ p^{r-1}(1-q^s)}{p^{r-1}+q^{s-1} - p^{r-1}q^{s-1}}$$