By Arthur R. Kopp 03/20/15

artsown@ptd.net
The term 'run' refers to a series of identical outcomes of random events. Tosses of a fair coin are random events, and
ten heads or eight tails in a row are series of identical outcomes . Runs are often called 'streaks', especially by gamers.

Within the past few years, methods of analysis have been derived leading to algorithms that compute probabilites of runs. I'll
use the term 'general' to characterize algorithms that allow entering any probability between zero and one to specify the
probability of success on each trial.

One general approach I've found is treated here: recurse

Another general method is here: RUNS
The author shows his derivation and also offers a calculator using his algorithm on the same page. He seems to be unaware that he
has unnecessarily limited the input and usefulness of his creation. My js implementation is discussed here:
runsx My DOS version can be downloaded here: RUNS-X.EXE

The fibonacci n-step method: fibonacci is precise but specific to only 0.5
for the probability of success on any trial.

In a different vein, I developed a runs analysis method for use with random bits files: TRAND
The Poisson distribution method used there is a example of a approximate and specific method. The approximate formula discussed
below is general.

------------------------------------------------------------------------------------------------------------------------------------------

Notes on the birth of my approximate formula

The basic idea behind this formula is discussed at the beginning of my TRAND page. In that case, I was only interested in
random bits (the binary or 'coin toss' applications). Consideration of runs patterns led to

N / 2 ^ (K +1) where K is run length, which can be viewed as the mean (λ) of a Poisson distribution. For small λ only the x = 0 term is required for the purpose. Then the probability p of at least one run is

1 - e ^ - λ

Recently, I started playing with D = 3, 4, 5, 6, .... as the number of possible outcomes on each trial. I used

λ = z * N / D ^ K and
attemped various z(D) until a close match to a 'exact' calculation was found. Oddly, I noticed a pattern. I discovered z(D) = (D - 1) / D works! So for λ I had

(D - 1) * N / D ^ (K + 1)

My next step was to generalize further and input Px between zero and one as the probability of success on any single trial. Then D = 1 / Px also works.
So I wound up with the kind of generality of inputs and applications I really wanted.

A technique can be used of partnering this formula with a precise method. When the # of trials exceeds 100,000 for example, there is no need to use
the precise method since this approximate method affords more than enough accuracy. That's what I've done with the calculators at my recurse,
runsx and fibonacci pages. Below is the simple formula as a javascript function. The values entry code disallows p < 0.0001

function a(N,K,p){

D = 1 / p;

num = (D -1) * N;

den = Math.pow(D, K + 1);

x = - num / den;

eps = Math.E;

result = 1 - Math.pow(eps , x);

return result;

}