# What is the probability that a run of $n$ consecutive successes occurs before a run of $m$ consecutive failures?

This example comes from the book "A First Course in Probability" by Sheldon Ross, Chapter 3, Section 3.5, Example 5C, Page 95. The example is given a solution but there is a part that I don't really understand. I hope someone can explain the logic to me.

The original question is as follow:

Independent trials, each resulting in a success with probability $p$ or a failure with probability $q = (1-p)$, are performed. We are interested in computing the probability that a run of $n$ consecutive successes occurs and before a run of $m$ consecutive failures. We are given the solution as follow:

Solution.: Let E be the event that a run of $n$ consecutive successes occurs before a run of $m$ consecutive failures. To obtain P(E), we start by conditioning on the outcomes of the first trial. That is letting H denote the event that the first trial results in a success, we obtain $$P(E) = pP(E|H)+qP(E|\bar H)$$ Now, given that the first trial was successful, one way we can get a run of $n$ successes before a run of $m$ failures would be to have the next $n-1$ trials all result in successes. So, let us condition on whether or not that occurs. That is, letting F be the event that trials 2 through n all are successes, we obtain $$P(E|H) = P(E|FH)P(F|H)+ P(E|\bar{F}H)P(\bar{F}|H)$$ On the one hand, clearly, P(E|FH) = 1; on the other hand, if the event $\bar{F}H$ occurs, then the first trial would result in a success, but there would be a failure some time during the next $n-1$ trials. However, when this failure occurs, it would wipe out all of the previous successes, and the situation would be exactly as if we started out with a failure. Hence, $$P(E|\bar{F}H) = P(E|\bar{H})$$ Pause !! This is the part where I don't really understand. I agree that when this failure occurs, it would wipe out all of the previous successes. But the situation for E to occur shouldn't be exactly the same as if we started out with a failure because if $F$ is the event that trials $2$ to $n$ are successes, then $\bar{F}$ is the event where not all $2$ to $n$ trials are successes. That being said, the last next $n-1$ trials could be successes. As an example, if the last two of $n-1$ trials is a failure then a success; then the situation for E to occur should be exactly the same as $P(E|H)$. So, can someone explain to me why $P(E|\bar{F}H) = P(E|\bar{H})$ ?

• Shouldn't $P(\overline{F}H)$ be $P(\overline{F}|H)$ instead, in the second equation? You condition $P(.|H)$ on $F$. Otherwise the whole second product would reduce to $P(E)$. – Henno Brandsma May 16 '17 at 8:02
• @HennoBrandsma Thanks for noticing the error. I have edited the second equation. – M.A.N May 16 '17 at 8:29

Since we are looking at an infinite number of trials, after removing a finite prefix of trials, we still have an infinite number of trials. Therefore, we can simply ignore this prefix for the probability of $E$ (even the conditions for $E$ would already be fulfilled by the prefix) and therefore $P(E) = P(E \mid B)$ for any event $B$ that restricts the outcomes of the trials only for a finite prefix.

This hopefully answers your question, but the partial solution you gave above seems rather complicated to me. Thankfully, I was able to find a pdf version of the book via Google. There, the author gives a rather complicated probability for $P(E)$ (not included in your question). That surprised me, because intuitively I thought, $P(E) = 1$.

Thinking about that in more detail, I am now convinced that, indeed, $P(E) = 1$: Let $A$ be the event, that we consecutively have $n$ successes and $m$ failures in $n + m$ trials. Clearly, $P(A) ≠ 0$, because $P(A) = p^n ⋅ q^m$ (assuming $0 < p < 1$).

Now let us iterate these $n + m$ trials and let $E'$ be the event that event $A$ occurs in the first block of $n + m$ trials, or in the second block of $n + m$ trials, or in the third block, etc. Since $P(A) ≠ 0$ and therefore $P(\overline{A}) ≠ 1$ it is easy to see that $P(\overline{E'}) = 0$, since we are looking at an infinite number of trials. Therefore we have $P(E') = 1$.

Since $E' ⊆ E$, it follows that also $P(E) = 1$.

For short: In an infinite sequence of trials you are able to find any finite pattern with probability $1$.

Therefore I suspect that there is a mistake in the solution in the book – unless I made a mistake myself or misunderstood the problem.

• Would you mind posting the pdf of the book you found? – Jason May 16 '17 at 15:07
• zalsiary.kau.edu.sa/Files/0009120/Files/… – Toni Dietze May 16 '17 at 15:24
• Thanks, I appreciate it. I've had a quick read and there seems to be numerous errors, and the problem is not very well defined. Your answer seems much better. I'll have a closer read and possibly post my own answer. – Jason May 16 '17 at 16:44

I have received a clear explanation and I thought it will be useful to share it out here. $$P(E|\bar{F}H) = P(E|\bar{H})$$ Because, we are not conditioning on the the results of trials 2 through n but rather just on whether they were all successes. That is, we are using

$$P(E|H) = P(E|FH) P(F|H) + P(E|\bar{F} H) P(\bar{F}|H)$$

so in determining $P(E|\bar{F} H)$ we do not know the results of trials 2 through n but only that they were not all heads, that is, that at least one was a tail. Because we know nothing about the sequence following that tail $$P(E|\bar{F} H) = P(E|\bar{H})$$

@Toni Your answer is correct if the question is asking the probability of $$n$$ consecutive successes ever occurs before $$m$$ consecutive failures, i.e. trials do not stop after condition is satisfied. I think the question, may it be phrased ambiguously, was asking if either $$n$$ consecutive successes of $$m$$ failures appear, the game stops. If we play such games a large number of times, what's the probability that the game ends with n consecutive successes.

@OP To clarify further, let's draw from the example OP provided where the last two trials of $$2^{nd}$$ to $$n^{th}$$ were failure and then success respectively. You argued that if the next $$n-1$$ trials are success, this is equivalent to $$P(E|H)$$.

The problem of this argument is that conditioning on $$\bar{F}$$ does not mean conditioning on the full realization of the $$2^{nd}$$ to $$n^{th}$$ trials, but only on if all or not all are successes, i.e. the conditioning doesn't mean the game has proceeded to the point where the $$2^{nd}$$ to $$n^{th}$$ trials are all tried. If we ever get a failure within the $$2^{nd}$$ to $$n^{th}$$ trials at some point, we are already in the event space defined by $$\bar{F}$$, then $$P(E|\bar{F}H)$$ in this case would be conditioning on from that failure. Since whatever happens before that failure is now irrelevant, that's the reason why $$P(E|\bar{F}H)$$ is exactly the same as $$P(E|\bar{H})$$.

There are several errors which suggest a fundamental misunderstanding of probability on the behalf of the author of this textbook. For starters, this problem is not properly defined - how many trials are there in total? Are we talking about precisely $n+m$ trials, or perhaps some finite number $N>n+m$, or an infinite sequence? The worked solution is inconsistent in which assumption it is using, and arrives at a conclusion which is incorrect regardless of which assumption we use. Let's go through it:

• "One the one hand, clearly, $P(E|FH)=1$" - nope. $E$ is the event that we have $n$ successes followed by $m$ failures; $H$ is the event that the first trial is a success; $F$ is the event that the second through $n^\text{th}$ trials are successes. If we are assuming precisely $n+m$ trials, then given $F,H$, the event $E$ occurs if and only if trial $n+1$ through $m$ are failures. This clearly has probability less than $1$. Similarly, this will be less than $1$ (but larger than $P(E)$) if we have $N>n+m$ trials. If we have an infinite number, then yes, this probability will be $1$; but this is no more "clear" than the original problem.

• "Hence, $P(E|F^cH)=P(E|H^c)$" - what?! You gave a very simple counterexample which shows this is not the case. The instance of the first failure indeed "resets" the count in a sense, but we might have only a single failure on the second trial, in which case we still have $n-2$ successes in a row. If we are assuming $n+m$ trials, the probability is already zero; if we are assuming $N>n+m+1$, this situation leaves us with a positive probability (whereas a later failure may make the probability zero) and if we are assuming infinitely many trials, then as before, each side is equal to $1$. (As Tony Dietze points out, since $E$ is an event only interested in the existence of a certain string, $P(E|C)=1$ for any event $C$ which depends only on finitely many trials.)

• "Now, $GH^c$ is the event that the first $m$ trials all result in failures, so $P(E|GH^c) = 0$" - why? This is true if we have only $n+m$ trials, but then, $P(E|C)=0$ for any event $C$ which includes a failure in the first $n$ trials. In general, this statement is only true if we have $N<n+2m$ total trials. The event $G$ is also an extremely strange event to condition on - why should we care if all the first $m$ trials are failures? Isn't one enough? Additionally, the author makes the same weird error as before, namely asserting that $G^cH^c$ involves a success wiping out all the previous failures and so claiming that $P(E|G^cH^c)=P(E|H)$. Absolute nonsense.

• "Thus, $P(E)=\ldots=\frac{p^{n-1}(1-q^m)}{p^{n-1}+q^{m-1}-p^{n-1}q^{m-1}}$" - clearly not true. If there $n+m$ trials, then $E$ is precisely the event where the first $n$ are success, and the rest are failures, so $P(E)=p^nq^m$. If there are infinitely many trials, the reasoning Tony Dietze provided shows that $P(E)=1$ (intuitively speaking, if we run trials for long enough, eventually any finite string will appear). If there are $N>n+m$ trials, $P(E)=P_N(E)$ must depend on $N$ with $P_N(E)\to1$ as $N\to\infty$.

It really blows my mind that such bad mathematics could appear in a textbook. I have not read any other part of this book, but if this example is anything to go by, you should get rid of it immediately and find a new textbook on probability.