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?

  • 1
    $\begingroup$ 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?) $\endgroup$ – zoli Aug 11 '16 at 12:00
  • $\begingroup$ $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 $\endgroup$ – jlesuffleur Aug 11 '16 at 13:20
  • $\begingroup$ @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). $\endgroup$ – 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$.

  • $\begingroup$ 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 $\endgroup$ – kpv Aug 16 '16 at 17:02
  • $\begingroup$ 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. $\endgroup$ – kpv Aug 16 '16 at 23:48
  • $\begingroup$ 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) $\endgroup$ – kpv Aug 17 '16 at 15:35
  • $\begingroup$ 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. $\endgroup$ – Robert Israel Aug 17 '16 at 17:19
  • $\begingroup$ But in any case it's obvious that $a_N \to 1$ as $N \to \infty$. $\endgroup$ – Robert Israel Aug 17 '16 at 17:55

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.