# Easily calculable minimum probability for m or more consecutive outcomes

I have to calculate probability for m or more consecutive outcomes in a set of trials. The number of trials (N) is very large. There are only two outcomes O1 and O2. Probability p of O1 is 6204 in 6205 and probability of O2 is (1-p). Hence, probability of O1 is very large as compared to that of O2. The trials are independent.

I have to calculate the probability of (m or more) consecutive O1 outcomes.

I looked online and the formula/calculations are pretty complicated.

But I do not need the exact probability. If I can get bulk of it, will do for me. All I have to do, is to establish a minimum probability keeping the calculations simple.

So, I thought of adding following for my purpose -

First m outcomes can be all O1 followed by O2, with probability = $p^m$(1-p).

First m+1 outcomes can be all O1 followed by O2, with probability = $p^1p^m$(1-p).

First m+2 outcomes can be all O1 followed by O2, with probability = $p^2p^m$(1-p).

and so on ... and add them in the end.

If I continue this way, after some iterations, the values become so insignificantly small that it does not matter whether I continue further or stop there. But by that time, I have already achieved the minimum value I need to establish.

Question is - Is there any flaw in this logic for establishing a lower limit of probability for (m or more) consecutive O1s. If so, what is the flaw and what is its fix.

With N being large enough, would it be ok to apply same logic to last m, m+1, m+2 ... to double my lower limit?

• You did not take into account that consecutive $O_1$'s can occur during the $N$ trials not only at the beginning. And: if $N$ is large then there may occur multiple (separated) consecutive $O_1$ occurrences. (Or are you interested only in consecutive $O_1$'s only at the beginning?) – zoli Aug 11 '16 at 12:00
• $O_1$'s does not need to be followed by $O_2$ since you ask for m or more consecutives $O_1$. Then the formula for (at least) first m outcomes to $O_1$ is : $p^m$. Maybe this is already enough for your limit, if you want a higher limit you must consider $O_1$'s series that are not at the begining, as mentionned by @zoli – jlesuffleur Aug 11 '16 at 13:20
• @zoli:I mentioned that in the question. I am willing to ignore those that occur not in the begining, or not on the end. The question is - Is the sum of the probabilities I listed is <= the probability of (m or more consecutive O1s). – kpv Aug 11 '16 at 22:00

This can be modelled with a Markov chain with $m+1$ states. We are in state $i$, $0 \le i \le m-1$, if the preceding $i$ trials were all $O_1$ but we have not yet seen $m$ successive $O_1$'s, or in state $m$ if we have seen $m$ successive $O_1$'s. Thus we start in state $0$, and at each trial where we are not already in state $m$, if the outcome of the trial is $O_1$ we increase the state by $1$, otherwise we reset it to $0$. State $m$ is absorbing: once we're there we stay there. The transition matrix $P$ looks like

$$\pmatrix{ 1-p & p & 0 &\ldots& 0 & 0\cr 1-p & 0 & p &\ldots& 0 & 0\cr \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \cr 1-p & 0 & 0 & \ldots& p & 0\cr 1-p & 0 & 0 & \ldots & 0 & p\cr 0 & 0 & 0 & \ldots & 0 & 1\cr}$$

The probability that we have at least one run of $m$ consecutive $O_1$'s in $N$ trials is $P^{N}_{0,m}$. This can be computed using the eigenvalues and eigenvectors of $P$.

EDIT: For fixed $m$, the generating function of the sequence $P^{N}_{0,m}$ is $$g(x)= \sum_{N=0}^\infty P^{N}_{0,m} x^N = (I-xP)^{-1}_{0,m}$$ I get \eqalign{g(x) &= \dfrac{p^m x^m}{1 - (2-p) x + (1-p)^2 \sum_{j=2}^m p^{j-2} x^j + (1-p) p^{m-1} x^{m+1}}\cr &= \dfrac{p^m x^m (1-p x)} {(1-x)^2 + p^m (1-p) x^{m+1}(1-x)}}

This suggests the following recurrence method. Let \eqalign{a_0 &= \ldots = a_{m-1} = 0\cr a_m &= p^m \cr a_{m+1} &= (2-p) p^m\cr} and for $j$ from $m+2$ to $N$ take $$a_j = 2 a_{j-1} -a_{j-2} - p^m (1-p) (a_{j-m-1} - a_{j-m-2})$$

Then your desired probability is $a_N$. This is easily implemented in a spreadsheet.

EDIT: If $N$ is very large, there may be difficulties involving precision. Then you may want to use an asymptotic form of the result. If we write $$d(x) = 1 - (2-p) x + (1-p)^2 \sum_{j=2}^m p^{j-2} x^j + (1-p) p^{m-1} x^{m+1}$$ (the denominator of $g(x)$ in its first form) and assuming its roots $r_1, \ldots, r_{m+1}$ are all distinct we have $$g(x) = \sum_{i=1}^{m+1} \dfrac{p^m r_i^m}{d'(r_i) (x - r_i)}$$ so that $$a_N = \sum_{i=1}^{m+1} \dfrac{p^m}{d'(r_i) r_i^{N+1-m}}$$ The smallest root in absolute value is $1$, with $d'(1) = -p^m$, so $\lim_{N \to \infty} a_N = 1$ (which is obvious from the probabilistic formulation). The next-smallest root in absolute value will determine how rapidly $a_N$ approaches $1$ as $N \to \infty$.

• Hi Robert, Can this be calculated. Is there a tool that I can use. As the numbers are large, I am looking for a tool where I can pass N, m and p(success) and it gives me probability of (m or more consecutive successes).Will appreciate your help if you can – kpv Aug 16 '16 at 17:02
• Thanks Robert, I will calculate $a_N$ and update the question. Though spreadsheets (excel) does not handle more than 64K rows, but This is doable easily otherwise. – kpv Aug 16 '16 at 23:48
• Hi Robert, The calculated value is ~.2354. Does that mean, I have to do 4 experiments of N trials each in order to expect to see at least one string of m or more consecutive successes. Also, the value stopped increasing (within precision of my computer) somewhere before j = 600 million. That indicates increasing number of trials does not matter as much (in proportion). So, what would be the difference between 4 experiments of N each, or one experiment of 4N. N is not a factor in the formula except from range of j, which did not seem to matter after some time (~600 M) – kpv Aug 17 '16 at 15:35
• Precision can be a serious issue with these computations if $N$ is very large. For large $N$ it is better to use an asymptotic form. I'll edit. – Robert Israel Aug 17 '16 at 17:19
• But in any case it's obvious that $a_N \to 1$ as $N \to \infty$. – Robert Israel Aug 17 '16 at 17:55