Distribution of the number of trials required for the first occurrence of the event SSF Consider repeated independent trials of two outcomes S (success) or F (failure) with probabilities $p$ and $q$, respectively. Determine the distribution of the number of trials required for the first occurrence of the event SSF.
My effort:
$P(N=3)=p^2q$, $P(N=4)=p^2q$, $P(N=5)=p^2q$, $P(N=6)=(1-p^2q)p^2q$. When $N$ > 6, I tried to calculated $P(N=k+1)$ from $P(N=k)$. The last three events for $N=k$ is SSF. Replacing the final SF with SS and then following with F, I can get a case ending with SSSF for $N=k+1$. The probability of this case is $P(N=k)/(pq)\times p^2q=P(N=k)\times p$. The case ending with FSSF is difficult. In order to put a F at the $(k-2)$'th position, I need to make sure the previous two events are not SS. But having two SS at those positions is allowable for the $N=k$ case.
 A: Markov Chain Solution
Consider the 4-state discrete-time Markov chain $X = (X_0, X_1, X_2, \dots)$, with transition structure shown in the figure below:

We are interested in transitions from Start to state $F$. The transition probability matrix is
$$P = \begin{bmatrix}
q & p & 0 & 0 \\
q & 0 & p & 0 \\
0 & 0 & p & q \\
0 & 0 & 0 & 1
\end{bmatrix}.$$
$P(X_k = F \mid X_0 = \textrm{Start}) = P(N \leq k)$, since $F$ is an absorbing state. Any possible run of the Markov chain that begins with $X_0 = \textrm{Start}$ and has $X_k = F$ corresponds to a sequence of trials with $N \leq k$.
We can calculate $$P(X_k = F \mid X_0 = \textrm{Start}) = \left(P^k\right)_{1,4},$$ and since $$P(N = k) = P(N \leq k) - P(N \leq k-1),$$ we can obtain $$P(N = k) = \left(P^k\right)_{1,4} - \left(P^{k-1}\right)_{1,4} = \left(P^k - P^{k-1}\right)_{1,4}.$$

Recursive Solution
We can calculate $P(N=k)$ for any $k$ using a recursive formula with base cases:
$$P(N = 1) = 0,$$
$$P(N = 2) = 0.$$
Then for $3 \leq k$,
$$P(N = k) = qP(N = k-1) + pqP(N = k - 2) + p^2P(X = k - 2),$$
where $X \sim \textrm{Geom}(q)$, so $P(X = j) = p^{j-1}q$ for $1 \leq j$ and $P(X = j) = 0$ otherwise.
This formula derives from applying the Law of Total Probability to this tree diagram of the process:

So I'm conditioning on the following possible initial events:

*

*The first result was $F$ (with probability $q$),

*The first results were $SF$ (with probability $pq$), and

*The first results were $SS$ (with probability $p^2$).

In case 1, $P(N = k \mid \textrm{first result was } F) = P(N = k - 1)$ because we have just not made any progress towards $SSF$ with the first result, and there are now $k - 1$ trials remaining to get $SSF$.
In case 2, $P(N = k \mid \textrm{first results were } SF) = P(N = k - 2)$ by similar reasoning.
In case 3, we have started with $SS$ so we are just waiting to observe $F$ (we can observe any number of $S$s and we will still just be waiting for $F$). We will observe $F$ in one trial with probability $q$, in two trials with probability $pq$, in three trials with probability $p^2q$, and so on.
If you put that all together using the Law of Total Probability
$$P(N = k) = P(N = k \mid A_1) P(A_1) + P(N = k \mid A_2) P(A_2) + P(N = k \mid A_3) P(A_3),$$
where $A_1$, $A_2$, $A_3$ are the three possible initial events, then you get the recursive formula.
