It has been a long time since I've done probability so I am not sure which to do (if either are correct). Thank you for taking the time to look at my work.

Probability an event occurs is $70$%. I'm looking for the probability our event occurs three times in a row for sample size $n$.

$(.7)^3=.343$ is the probability to occur three consecutive times

$1-.343=.657$ would be the chance to fail.

First idea:

For $n=3$ our success rate is $.343$

$n=4$ we have two opportunities for success, thus $1-(.657)^2=.568351$

$n=5$, three opportunities for success, thus $1-(.657)^3=.71640$...

Generalization: Probability for success: $$1 - (.657)^{n-2}$$

Second idea:

Probability when $n=3$ would be $(.7)^3$

At $n=4$ we'd have $(.7)^3+(.3)(.7)^3$

For $n=5$ we'd have $(.7)^3+(.3)(.7)^3+(.3)^2(.7)^3+(.3)(.7)^4$

I'm leaning towards the second idea...but I'm failing to see a generalization for it.

Please excuse my LaTeX it has been a long time since I've asked/answered any questions. Thank you.

  • 1
    $\begingroup$ Should it be exactly three events, denoted by $1$, for example $00011100$ or does $01111000$ or $1110111$ count as well? $\endgroup$ – Michael Hoppe Jan 6 '17 at 18:32
  • $\begingroup$ They all count. Though, as long as three occur consecutively we don't care about the rest. For very large n the probability should approach 1, correct? If a generalization can be found I could find the size of n that all but guarantees a success. $\endgroup$ – Vincent Jan 7 '17 at 1:59
  • $\begingroup$ This has been asked several times here. See eg math.stackexchange.com/questions/514103/… math.stackexchange.com/questions/4658/… $\endgroup$ – leonbloy Jan 7 '17 at 12:05
  • $\begingroup$ Hi Vincent, I gave an alternative answer to your question, to provide a general formula for the probability as a function of the sample size. $\endgroup$ – Anatoly Jan 12 '17 at 13:28

Let's denote the event under consideration with $a$ \begin{align*} P(X=a)=0.7 \end{align*} and we denote the complementary event with $b$.

We are looking for the words of length $n$ and their probability of occurrence which do not contain three or more consecutive $a$'s. The result is $1$ minus this probability.

We can describe the set of these invalid words as the words built from the alphabet $V=\{a,b\}$ which contain at most one or two consecutive $a$'s.

These are words

  • starting with zero or more $b$'s:$$b^*$$

  • followed by zero or more occurrences of $a$ or $aa$ each followed by one or more $b$'s: $$(ab^+|aab^+)^*$$

  • and terminating with zero, one or two $a$'s $$(\varepsilon|a|aa)$$

We obtain

\begin{align*} b^*(ab^+|aab^+)^*(\varepsilon|a|aa)\tag{1} \end{align*}

The regular expression (1) generates all invalid words in a unique manner. In such cases we can use it to derive a generating function $$\sum_{n=0}^\infty a_n z^n$$ with $a_n$ giving the number of invalid words of length $n$.

In order to do so all we need to know is the geometric series expansion since the $star$ operator \begin{align*} a^*=\left(\varepsilon|a|a^2|a^3|\cdots\right)\qquad\text{ translates to }\qquad 1+z+z^2+z^3+\cdots=\frac{1}{1-z} \end{align*}

Accordingly $a^+=aa^*$ translates to $\frac{z}{1-z}$ and alternatives like $(\varepsilon|a|aa)$ can be written as $1+z+z^2$.

We translate the regular expression (1) into a generating function (by mixing up somewhat the symbolic to provide some intermediate steps).

Since we want to calculate the probabilities of occurrence of $P(X=a)$ we keep track of $a$ and $b$ by respecting them as corresponding factors in the generating function.

\begin{align*} b^*\left(ab^+|aab^+\right)^*(\varepsilon|a|aa) &\longrightarrow \quad \frac{1}{1-bz}\left(\left.\frac{abz^2}{1-bz}\right|\frac{a^2bz^3}{1-bz}\right)^*\left(1+az+a^2z^2\right)\\ &\longrightarrow \quad \frac{1}{1-bz}\left(\frac{abz^2+a^2bz^3}{1-bz}\right)^*(1+az+a^2z^2)\\ &\longrightarrow \quad \frac{1}{1-bz}\cdot\frac{1}{1-\frac{abz^2+a^2bz^3}{1-bz}}(1+az+a^2z^2)\\ &\quad\quad=\frac{1+az+a^2z^2}{1-bz-abz^2-a^2bz^3}\tag{1} \end{align*}

$$ $$

We conclude: The number of invalid words is given by (1). So, the number of valid words is the number of all words minus the number of invalid words. We obtain the generating function $A(z)$ \begin{align*} A(z)&=\sum_{n=0}^\infty(a+b)^nz^n-\frac{1+az+a^2z^2}{1-bz-az^2-a^2z^3}\\ &=\frac{1}{1-(a+b)z}-\frac{1+az+a^2z^2}{1-bz-az^2-a^2z^3}\\ &=\frac{a^3z^3}{(1-(a+b)z)(1-bz-abz^2-a^2bz^3)}\\ &=a^3z^3+a^3(a+2b)z^4+a^3(\color{blue}{1}a^2+\color{blue}{4}ab+\color{blue}{3}b^2)z^5\\ &\qquad a^3(a+b)^2(a+4b)z^6+a^3(a^4+7a^3b+18a^2b^2+16ab^3+5b^4)z^7+\cdots \end{align*}

The expansion was done with the help of Wolfram Alpha. We see that e.g. the number of valid words of length $5$ is $\color{blue}{1}+\color{blue}{4}+\color{blue}{3}=8$.

$$ $$

Out of $2^5=32$ binary words of length $5$ there are $8$ valid words which are marked $\color{blue}{\text{blue}}$ in the table below.

We obtain \begin{array}{cccc} \color{blue}{aaa}aa\qquad&ab\color{blue}{aaa}\qquad&b\color{blue}{aaa}a\qquad&bb\color{blue}{aaa}\\ \color{blue}{aaa}ab\qquad&abaab\qquad&b\color{blue}{aaa}b\qquad&bbaab\\ \color{blue}{aaa}ba\qquad&ababa\qquad&baaba\qquad&bbaba\\ \color{blue}{aaa}bb\qquad&ababb\qquad&baabb\qquad&bbabb\\ aabaa\qquad&abbaa\qquad&babaa\qquad&bbbaa\\ aabab\qquad&abbab\qquad&babab\qquad&bbbab\\ aabba\qquad&abbba\qquad&babba\qquad&bbbba\\ aabbb\qquad&abbbb\qquad&babbb\qquad&bbbbb\\ \end{array}

We denote with $[z^n]$ the coefficient of $z^n$ in a series.

We conclude

  • The number of occurrences of wanted words of size $n$ is the coefficient of $z^n$ of $A(z)$ evaluated at $a=b=1$ and given as OEIS sequence 050231.

\begin{align*} \left.[z^n]A(z)\right|_{a=b=1} \end{align*}

  • The wanted probability of valid words of size $n$ is the coefficient of $z^n$ of $A(z)$ evaluated at $a=0.7,b=0.3$. \begin{align*} \left.[z^n]A(z)\right|_{a=0.7,b=0.3} \end{align*}

  • We obtain for $n=0$ up to $n=7$ \begin{array}{c|cl} n&\left.[z^n]A(z)\right|_{a=b=1}&\left.[z^n]A(z)\right|_{a=0.7,b=0.3}\\ \hline 0&0&0\\ 1&0&0\\ 2&0&0\\ 3&1&0.343\\ 4&3&0.4459\\ 5&8&0.5488\\ 6&20&0.6517\\ 7&47&0.7193\\ \end{array}

  • $\begingroup$ @Vincent: Thanks a lot for granting the bounty! :-) $\endgroup$ – Markus Scheuer Jan 11 '17 at 5:33

The issue with looking at opportunities for success is that they are not completely independent. For example, in a row of size 4, if the first three aren't all successes, this greatly decreases the chance that the last three aren't all successes (the only way this can happen is if only the first trial was a failure).

You can still get this approach to work (via correcting for events which are dependent via some sort of inclusion-exclusion), but generally a cleaner method for these types of problems is to write down a recurrence (or more generally, model them as a finite state Markov chain).

Let's let $P(N)$ be the probability a row of length $N$ has no 3 consecutive successes. To help us write down a recurrence, we'll break $P(N)$ down into 3 smaller probabilities. Let's let $P(N, 0)$ be the probability a row of length $N$ has no 3 consecutive successes AND that the last attempt was a failure. Similarly, let $P(N,1)$ be the probability that a row of length $N$ has no 3 consecutive successes AND that the last attempt was a success, but the second-last attempt was a failure, and finally, let $P(N,2)$ be the probability that a row of length $N$ has no 3 consecutive successes AND the last two attempts were successes, but the third-to-last attempt was a failure. Intuitively, these different cases measure how "close" we are to getting 3 successes in a row. It's not too hard to see that $P(N) = P(N,0) + P(N,1) + P(N,2)$, since if the last three attempts are all successes, you've already won.

Now, let's try to write $P(N+1, 0)$ in terms of smaller cases. The probability you have no 3 consecutive successes in a row of length $N+1$ and that your last attempt was a failure is simply the probability that there are no 3 consecutive successes in the first $N$ tries and that you fail the $N+1$st try. This gives us the equation:

$$P(N+1,0) = 0.3P(N) = 0.3P(N,0) + 0.3P(N,1) + 0.3P(N,2)$$

Via similar logic, we can show that $P(N+1,1)$ and $P(N+1,2)$ satisfy the following equations:

$$P(N+1,1) = 0.7P(N, 0)$$


$$P(N+1,2) = 0.7P(N, 1)$$

Substituting these into the original equation for $P(N+1,0)$, we get:

$$P(N+1, 0) = 0.3P(N,0) + 0.21P(N-1, 0) + 0.147P(N-2,0)$$

Now, this is just a standard linear recurrence relation. If $\lambda_1$, $\lambda_2$, and $\lambda_3$ are the roots of $z^3 - 0.3z^2-0.21z-0.147=0$, then there are some constants $a_1, a_2, a_3$ which you can solve for so that

$$P(N, 0) = a_1\lambda_1^N + a_2\lambda_2^N + a_3\lambda_3^N$$

Since $P(N) = P(N+1,0)/0.3$, this gives a similar formula for $P(N)$ (and ultimately for $1-P(N)$, the probability a success does occur 3 consecutive times).

  • $\begingroup$ Thanks for replying. I'll have to wait until the morning to see if I understand...bit tired now. I hadn't considered this question being quite as in depth as it appears. $\endgroup$ – Vincent Jan 4 '17 at 8:15

I would propose an alternative - maybe easier - approach, trying to give a formula that provides a generalized answer for the probability of three events in a row, given the probability $p $ that the event occurs, as a function of the sample size $n$. As shown below, this approach may also be useful to determine an additional issue of this problem highlihted in one of the comments, i.e. the sample size needed to "guarantee" a success with a given confidence level.

Let us call $P (n) $ the probability that our event occurs three times in a row within a sequence of $n $ trials. Also, for each trial, let us denote as Y the case that the our event occurs, and as N the case that it does not occur. So, in the specific case described in the OP, we are looking for the probability of getting a triple YYY in a sequence of $n $ elements when $p=0.7$.

As a general rule, we can note that, passing from a sample size $n $ to a sample size $n+1$, the probability that our event occurs three times in a row increases only because there is the possibility that the triple YYY, not obtained in the first $n $ trials, occurs as a final triple in the sequence of $n+1$ trials. So, to calculate $P (n+1 )$ from $ P (n) $, we simply have to add the probability that the triple in a row is not obtained until a final sequence NYYY. Note that the N preceding the triple YYY is strictly necessary to satisfy the condition that the triple has not been obtained in the first $n $ trials.

We can then start with $n=3$, for which we trivially have $P (3)=p^3$. For $n=4$, we have to add to $P (3) $ the probability to get a sequence NYYY, i.e. we have to add $p^3(1-p)$. Similarly, for $n=5$, we have to add to $P (4) $ the probability to get a final sequence NYYY (note that this is not affected by what happens in the first of the five trials), which means that we must add $p^3(1-p)$ as in the previous case. Lastly, for $n=6$, we have again to add to $P (5) $ the probability to get a final sequence NYYY (note that, as above, this is not affected by what happens in the first and in the second of the six trials). This leads to a further increase by $p^3(1-p)$. So, for this initial group of four values of in our probability progression, we directly obtain the recurrence

$$P (n+1)=P (n)+ p^3 (1-p)\,\,\,\, \text {(for n=3 to 6)}$$

Accordingly, for the specific case $p=0.7$, this formula gives the initial values

\begin{aligned} P(3) & =0.7^3=0.343 \\ P (4) & = 0.7^3+0.3 \cdot 0.7^3 = 0.4459 \\ P (5) & = 0.7^3+2\cdot 0.3 \cdot 0.7^3 = 0.5488 \\ P (6) & = 0.7^3+3\cdot 0.3 \cdot 0.7^3 = 0.6517 \\ \end{aligned}

already obtained in a previous answer via a different method.

Now let us consider the values of $n \geq 7$. Here something changes, because the fact that the sequence ends with NYYY does not imply that the triple YYY has not occurred before, i.e. in the first $n-4$ trials. So, at each step, the probability of getting a final NYYY must be multiplied to the probability of failure in the first $n-4$ trials, which is $1-P (n-4 ) $. Therefore, for $n=7$ we have to add to $P (6) $ the probability given by $p^3(1-p) [1-P(3)]\,\,$, for $n=8$ we have to add to $P (7) $ the probability given by $p^3(1-p) [1-P(4)] \,\, $, and so on. This leads to the recurrence

$$P (n+1)=P (n)+ p^3(1-p)[1-P(n-4)]\,\,\,\, \text{(for n}\, \geq \text {7)}$$

We can now try to get a closed form for this last recurrence. Let us set, by simplicity, $p^3=j$ and $(1-p) =k \,\, $. The recurrence becomes

$$P (n+1)=P (n)+ jk-jk \,P(n-4)\, \,$$

Note that the four values of $P (n)$ already determined can be written as $$P (3)=j $$ $$P (4)=j +jk$$ $$P (5)=j +2jk$$ $$P (6)=j +3jk$$

so that they contain only terms of degree $j $ or $jk $. Continuing our probability progression and focusing on the second group of four values of $n$ (from $n=7\,\, $ to $n=10 \,\, $), new terms of degree $j^2k $ and $j^2k^2$ appear applying the recurrence above (for the sake of readability, here I directly provide the resulting expressions avoiding the rather tedious step-by-step calcuations):

\begin{aligned} P (7) & = P(6)+ jk-jk P (3)=j+4jk-j^2k \\ P (8) & = P(7)+ jk-jk P (4)= j+ 5jk -2j^2k-j^2k^2 \\ P (9) & = P(8) + jk-jk P (5)= j+ 6jk -3j^2k-3j^2k^2 \\ P (10) & = P (9) + jk-jk P (6)= j+ 7jk -4j^2k-6j^2k^2 \\ \end{aligned}

Some pattern begins to emerge in these expansions. For the specific case $p=0.7$, $$P (7)\approx 0.7193$$ $$P (8)\approx 0.7763$$ $$P (9) \approx 0.8228$$ $$P (10) \approx 0.8586$$

We can repeat the procedure, applying the same recurrence and continuing with the third group of four values of $n $ (i.e., $n=11$ to $14$). Again, new terms appear, in this case of degree $j^3k^2$ and $j^3 k^3$ (as above, I directly provide the resulting expressions):

\begin{align*} P(11) &=j+8jk-5j^2k-10j^2k^2+j^3k^2 \\ P(12) &=j+9jk-6j^2k-15j^2k^2+3j^3k^2+j^3k^3 \\P(13) & = j+10jk-7j^2k -21j^2k^2+6j^3k^2+4j^3k^3 \\ P (14) & = j+11jk-8j^2k-28j^2k^2+10j^3k^2+10j^3k^3\\ \end{align*}

The final pattern is therefore as follows. Our expansions of $P (n) $ include:

  • in the odd positions, $\lfloor (n+1)/4 \rfloor \,\, $ terms of the form $$(-1)^{i-1} \binom{n-3i}{i-1} j^i k^{i-1} \,\, $$ where $$i=1,2... \lfloor (n+1)/4 \rfloor \,\, $$ For example, in the expansion of $P (14)$ there are $ \lfloor (14+1)/4 \rfloor =3 \, \,\, $ terms of this form, which are $j $, $-8j^2k $, and $10 j^3k^2$;

  • in the even positions, $\lfloor n/4 \rfloor \,\, $ terms of the form $$(-1)^{i-1} \binom{n-3i}{i} j^i k^i \,\, $$ where $$i=1,2... \lfloor n/4 \rfloor$$

    Accordingly, taking again for example the expansion of $P (14)$, there are $ \lfloor 14/4 \rfloor =3 \,$ terms of this form, which are $11jk$, $-28j^2k^2$, and $10 j^3k^3$.

Therefore, we obtain the following general expression for $P (n) $:

$$P (n)=\sum_{i}^{\lfloor (n+1)/4 \rfloor } (-1)^{i-1} \binom{n-3i}{i-1} j^{i}k^{i-1} +\sum_{i}^{\lfloor n/4 \rfloor } (-1)^{i-1} \binom{n-3i}{i} j^i k^i $$

Reminding that $j=p^3$ and $k=(1-p) $, we finally get

$$P (n)=\sum_{i}^{\lfloor (n+1)/4 \rfloor } (-1)^{i-1} \binom{n-3i}{i-1} p^{3i}(1-p)^{i-1} + \sum_{i}^{\lfloor n/4 \rfloor } (-1)^{i-1} \binom{n-3i}{i} p^{3i} (1-p)^i $$

Setting $p=0.7$, we obtain the probability asked in the OP for, which is

$$P (n)=\sum_{i}^{\lfloor (n+1)/4 \rfloor } (-1)^{i-1} \binom{n-3i}{i-1} 0.7^{3i} \cdot 0.3^{i-1} + \sum_{i}^{\lfloor n/4 \rfloor } (-1)^{i-1} \binom{n-3i}{i} 0.7^{3i}\cdot 0.3^i $$

Also note that the two sums have the same number of terms when $n \not\equiv -1 \,\, \text {mod}\,\, 4$, whereas the first sum has one term more than the second one when $n \equiv -1 \,\,\text {mod} \, 4$, because in this case $(n+1)/4$ is integer. This term is given by

$$\displaystyle (-1)^{\frac{(n+1)}{4}-1} \binom{n-\frac{3(n+1)}{4}}{ \frac{(n+1)}{4}-1}\, 0.7^{\frac{3(n+1)}{4}} \, 0.3^{\frac{(n+1)}{4}} $$ $$\displaystyle = (-1)^{\frac{(n-3)}{4}} \binom{\frac{(n-3)}{4}}{\frac{(n-3)}{4}}\, 0.7^{\frac{3(n+1)}{4}} \, 0.3^{\frac{(n+1)}{4}} $$ $$\displaystyle = (-1)^{\frac{(n-3)}{4}} \, 0.7^{\frac{3(n+1)}{4}} \, 0.3^{\frac{(n+1)}{4}} $$

So the probability asked in the OP can be alternatively expressed as

$$P (n)=\sum_{i}^{\lfloor n/4 \rfloor } (-1)^{i-1} \binom{n-3i}{i}\, 0.7^{3i}\, 0.3^{i} \left( \frac {i}{0.3(n-4 i+1)} +1 \right) + S$$


$$S = \begin{cases} 0 & \mbox{if } n \not\equiv -1 \, \text {mod}\, 4\\ (-1)^{\frac{(n-3)}{4}} \, 0.7^{\frac{3(n+1)}{4}} \, 0.3^{\frac{(n+1)}{4}} & \mbox{if } n \equiv -1 \, \text {mod}\, 4 \end{cases}$$

It could also be observed that $|S|$ is relatively small and rapidly decreases for increasing $n$: its value is $\approx 0.0106\, \,\, $ for $n=7$, becoming $\approx 0.00109\, \,\, $ for $n=11$ and $\approx 0.000112\,\,\, $ for $n=15$, so that its contribute to the overall probability is nearly negligible. The last expansion without the $S$ term can therefore considered a valid approximation even for the case $n \equiv -1 \, \text {mod}\, 4$.

The probability of three events in a row given by these formulas for $p=0.7$ and $n=3$ to $10$ have already been provided above. As expected, for increasing $n $, the value of $P (n)$ approaches $1$. The first value for which the probability achieves $95\%$ is $n=15$, since $P (15) \approx 0.9553\,\,\, $, as confirmed by WA here. The probability achieves $97.5\%$ and $99\%$ for $n=18$ and $n=22$, respectively, since $P(18) \approx 0.9772\,\,\, $ and $P(22) \approx 0.9909\,\,\, $, as confirmed by WA here and here.


Let $p=0.7$ be the probability of success, $\mathrm{f}(n)$ be the probability of a sequence of length $n$ having 3 consecutive successes and $\mathrm{g}(n)=1-\mathrm{f}(n)$, where $\mathrm{g}(n)$ corresponds to the probability of a sequence of length $n$ having at most 2 consecutive successes.

It holds $\mathrm{g}(0) = \mathrm{g}(1) = \mathrm{g}(2) = 1$.

Then $\mathrm{g}(n) = (1-p)\mathrm{g}(n-1) + (1-p)p\mathrm{g}(n-2) + (1-p)p^2\mathrm{g}(n-3)$.

This holds because all sequences of length $n$ that have at most 2 consecutive successes can be constructed from (1) all such sequences of length $n-1$ suffixed by a failure plus; (2) all such sequences of length $n-2$ suffixed by a failure and a success, plus; (3) all such sequences of length $n-3$ suffixed by a failure and two successes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.