Distribution of the number of trials required for the first occurrence of the event 50 S containing at least one SSSSS. 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 50 S containing at least one SSSSS, i.e., totally 50 successes and the 5 successive successes should happen at least one time.
My efforts:
Let $M_n$ be the number of trials required for the first occurrence of totally $n$ S. We have calculated that $P(M_n=k)={k-1\choose n-1}p^{n}q^{k-n}$. Let $N_n$ be the number of trials required for the first occurrence of totally $n$ S containing at least one SSSSS. Then $P(N_n=k)=0$ if $n<5$. We want to determine the distribution of $N_{50}$.
Condition on the following possible initial events:

*

*A1: The first five results were Fxxxx (with probability $q$ ), x = S or F,

*A2: The first five results were SFxxx (with probability $pq$ ),

*A3: The first five results were SSFxx (with probability $p^2q$),

*A4: The first five results were SSSFx (with probability $p^3q$),

*A5: The first five results were SSSSF (with probability $p^4q$),

*A6: The first five results were SSSSS (with probability $p^5$).

Note that $P(A_1)+P(A_2)+P(A_3)+P(A_4) +P(A_5)+P(A_6)=1$.
Let $k>5$.
In case 1, $P(N_n=k∣\text{first result was F})=P(N_n=k−1)$ because we have just not made any progress towards $n$ S containing SSSSS with the first result, and there are now $k−1$ trials remaining to get $n$ S containing SSSSS.
In case 2, $P(N_n=k∣\text{first two results were SF})=P(N_{n-1}=k−2)$. Although we have just not made any progress towards SSSSS with the first two results, but we do have a S and there is $(n-1)$ S remaining. There are now $k−2$ trials remaining to get $(n-1)$ S containing SSSSS.
In case 3, $P(N_n=k∣\text{first three results were SSF})=P(N_{n-2} =k−3)$. Although we have just not made any progress towards SSSSS with the first three results, but we do have two S and there is $(n-2)$ S remaining. There are now $k−3$ trials remaining to get $(n-2)$ S containing SSSSS.
In case 4, $P(N_n=k∣\text{first four results were SSSF})=P(N_{n-3} =k−4)$. Although we have just not made any progress towards SSSSS with the first four results, but we do have three S and there is $(n-3)$ S remaining. There are now $k−4$ trials remaining to get $(n-3)$ S containing SSSSS.
In case 5, $P(N_n=k∣\text{first five results were SSSSF})=P(N_{n-4} =k−5)$. Although we have just not made any progress towards SSSSS with the first five results, but we do have four S and there is $(n-4)$ S remaining. There are now $k−5$ trials remaining to get $(n-4)$ S containing SSSSS.
In case 6, $P(N_n=k\mid\text{first five results were SSSSS})=P(M_{n-5}=k−5)$. We already have SSSSS. We no longer need to worry about SSSSS. We just need to get $(n-5)$ S and we are done. There are now $k−5$ trials remaining to get $(n-5)$ S.
If you put that all together using the Law of Total Probability
$$P(N_n =k)=P(N_n =k\mid A_1)P(A_1)+P(N_n =k\mid A_2)P(A_2)+
+\cdots+P(N_n =k\mid A_6)P(A_6),$$
where $A_1, A_2, A_3, \ldots, A_6$ are the 6 possible initial events, then you get the recursive formula for $k> 5$,
$$P(N_n =k)=qP(N_n =k−1)+pqP(N_{n-1} =k−2)+p^2qP(N_{n-2} =k−3) 
+\cdots+ p^4qP(N_{n-4} =k−5)+p^5P(M_{n-5}=k−5)$$
Am I on the correct track? Some strange things happen when I tried to calculate the base case $P(N_5=k)$. Please tell me what is $P(N_5=k)$ and help me verify the recursive relation for $P(N_6=k)$.
 A: a) Your approach to deduce the recurrence is correct, the problem is to fix the appropriated initial conditions and bounds of validity.
b) To the purpose of solving that clearly we need to proceed as follows.
Given a sequence of Bernoulli trials, with probability of success  $p$ (failure $q=(1-p)$), allow me
to represent that by a binary string $1 = $ success, $0 =$ failure so as to keep congruence with other posts I am
going to link to.
For the same reason and for putting your recurrence with proper initial conditions, allow me to change your denominations
and consider

the binary strings of length $n$, having $m$ zeros and $s$ ones, including a one which is fixed at the end of the string;
also let' go general and consider run of consecutive ones of length $r$.

We indicate as
$$
P(s,r,n) = N_c (s,r,n)\, p^{\,s } q^{\,n - s} 
$$
the probability that in a string of length $n$, with total $s$ ones and terminating with a one,
there might be runs of consecutive ones of length $r$ or greater.
Now your recurrence reads
$$
\eqalign{
  & P(s,r,n) = q\,P(s,r,n - 1) + pq\,P(s - 1,r,n - 2) + p^{\,2} q\,P(s - 1,r,n - 2) +   \cr 
  &  +  \cdots  + p^{\,4} q\,P(s - r + 1,r,n - r) + \left( \matrix{
  n - 1 - r \hfill \cr 
  s - 1 - r \hfill \cr}  \right)p^{\,s} q^{\,n - s}  \cr} 
$$
Note that each term is a homogeneous polynomial in $p^s\, q^{n-s}$, so we do not need to bring them around and
we can profitably concentrate on the number of strings given by $N_c$, that is
$$ \bbox[lightyellow] {  
\eqalign{
  & N_c (s,r,n) =   \cr 
  &  = \left\{ {\matrix{   1 & {\left| \matrix{  \;0 \le r \le s \hfill \cr 
  \;1 \le s = n \hfill \cr}  \right.}  \cr 
   {\sum\limits_{k = 0}^{r - 1} {N_c (s - k,r,n - 1 - k)} 
 + \binom{  n - r - 1 }{   s - r - 1 }  }
 & {\left| \matrix{  \;0 \le r \le s \hfill \cr   \;1 \le s < n \hfill \cr}  \right.}  \cr 
   0 & {{\rm otherwise}}  \cr 
 } } \right. \cr} 
 } \tag{1}$$
Regarding the conditions,

*

*the case $s=n$ was not covered in the construction, and must be added;

*because of the one in last position, $s$ shall be greater than $1$;

*the remaining are obvious.

The recurrence above has been checked with direct computation for the smaller values of the parameters.
Example:

c) The recurrence (1) can solved in a closed form as a finite sum.
Consider in fact the strings of this type

Their total number is $\binom{n}{s}$ and  those having a run of length $r$ or greater are $N_c (s+1,r, n+1)$.
Therefore, the complement of $N_c$ will represent the strings of the same architecture, which
have runs up to $r-1$.
The number of strings composed as above but excluding the last one, which have runs of length up to $r-1$
is given by
$$
N_b (s,r - 1,m + 1)
$$
where
$$
N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers  }s,m,r} \right.\quad  =
\sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} 
{\left( { - 1} \right)^k \binom{m}{k}
 \binom
 { s + m - 1 - k\left( {r + 1} \right) } 
 { s - k\left( {r + 1} \right)}\ }
$$
as explained in various posts, refer mainly to this and to this other one.
But because of the presence of the one at the end, we have to deduct from the above
the strings which end in zero plus $ r-1$ ones, giving a final run of $r$.
These are
$$
N_b (s-r+1,r - 1,m )
$$
and we conclude that
$$ \bbox[lightyellow] {  
\eqalign{
  & N_c (s + 1,r,n + 1) = N_c (s + 1,r,s + m + 1) =   \cr 
  &  = \left( \matrix{  s + m \cr   s \cr}  \right)
 - N_b (s,r - 1,m + 1) + N_b (s - r + 1,r - 1,m) =   \cr 
  &  = \left( \matrix{  n \cr   s \cr}  \right)
 - N_b (s,r - 1,n - s + 1) + N_b (s - r + 1,r - 1,n - s)
 \quad \left| {\;0 \le s,r,m} \right. \cr} 
 } \tag{2}$$
$N_b$ is more present in literature, has plenty of recurrent relations, and a simple o.g.f. .
Not to make the answer too long, I am not going further into details.
d) Summing on $n$.
Consider the strings composed as shown in the sketch in para. c) above.
Their total number is $\binom {s+m}{s} = \binom {n}{s}$ and each has the same probability $p^{s+1}\, q^m = p^{s+1}\, q^{n-s}$.
Keeping $n$ fixed, and summing over $s$ we get
$$
\sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,n} \right)}
 {\binom{  n }{   s } p^{\,s + 1} q^{\,n - s} }
  = p\left( {p + q} \right)^{\,n}  = p
$$
which is obvious, since if we add the complementary strings ending in zero we get $(p+q)^{n+1} =1$.
Keeping instead $s$ fixed and summing on $n$, which means to sum on $m$, gives
$$
\eqalign{
  & \sum\limits_{\left( {0\, \le \,s\, \le } \right)\,n\,}
 {\binom{  n }{s} p ^{\,s + 1} q^{\,n - s} } 
 = \sum\limits_{\left( {0\, \le } \right)\,\,m\,}
 {\binom{  s + m }{m} p^{\,s + 1} q^{\,m} }  =   \cr 
  &  = p^{\,s + 1} \sum\limits_{\left( {0\, \le } \right)\,\,m\,}
 {\binom{   - s - 1 }{m} \left( { - 1} \right)^{\,m} q^{\,m} }
  = {{p^{\,s + 1} } \over {\left( {1 - q} \right)^{\,s + 1} }} = 1 \cr} 
$$
which is the Negative Binomial distribution.
Since, by  its combinatoric meaning we have
$$
\left\{ \matrix{
  0 \le N_c (s + 1,r,n + 1) \le N_c (s + 1,r - 1,n + 1) \le \binom{n }{ s } \hfill \cr 
  N_c (s + 1,s + 2,n + 1) = 0 \hfill \cr 
  N_c (s + 1,s + 1,n + 1) = 1 \hfill \cr 
  N_c (s + 1,1,n + 1) = \binom{n }{ s } \hfill \cr 
  N_c (s + 1,0,n + 1) = \binom{n }{ s } \hfill \cr
}  \right.
$$
then
$$
 0 \le P_c (s + 1,r,p) = \sum\limits_{\left( {0\, \le \,s\, \le } \right)\,n\,}
 {N_c (s + 1,r,n + 1)p^{\,s + 1} q^{\,n - s} }  \le 1
 \quad \left| \matrix{
  \,0 \le s \hfill \cr 
  \;0 \le r \le s + 1 \hfill \cr 
  \;0 < p < 1 \hfill \cr}  \right.
$$
converges (albeit slowly), and given $s,p$, it is a CDF in $(s+1-r)$ (in case with a further shift of the support).
Unfortunately, as to my knowledge, the sum in $n$ of $N_c$ (and of $N_b$) does not have a closed form : re. to this already cited post.
It is possible however to compute, from (2), a double o.g.f. if you are interested in.
A: There might be a simpler approach.
Let N be the number of trials and P(N) be its probability given the conditions above, then:
$$P(N) = \sum_{S \in S'} p^5\prod_{j \in S} q^{j} p_{j}$$
where S' is all integer partitions (and their other possible permutations with no repeated duplicate elements) of N-50 including zeroes with fixed length 45 and N>=50.
And in general, if want to find the distribution of N given that there in M successes and the presence of m successive  successes, then:
$$P(N) = \sum_{S \in S'} p^m \prod_{j \in S} q^{j} p_{j}$$
where S' is all integer partitions (and their other possible permutations with no repeated duplicate elements) of N-M including zeroes with fixed length N-m and N>=M.
P.S. It is not a closed for solution but it is useful enough and better than simulation.
