The probability of finding a string of n characters

I tried to google this today but I only found a lot of unnecessarily complicated stuff. I wanted something simple but mathematically exact so I had to figure out this myself.

 // p(n,m,b) - the probability of finding at least one occurence of a string of n characters (or digits/symbols)
 // (not starting and ending with the same character) in a larger random string of m characters
 // b - is the number of different types of characters
 double p(int n, int m, int b) { return f(n,m,b) / Math.Pow(b,m); }
 double f(int n, int m, int b) { return m<n ? 0 : b * f(n,m-1,b) + Math.Pow(b,m-n) - f(n,m-n,b); }

Compare this with the standard function for calculating an approximate probability…

double pa(int n, int m, int b) { return 1 - Math.Pow((Math.Pow(b,n)-1) / Math.Pow(b,n), m-n+1); }

The f-function above calculates the total number of possible ways that the the sought for string can appear in the larger random string. Although it’s pretty short it’s not particularly fast. I made a much faster algorithm based on this idea…

formula

For example: Let’s say you want to calculate the probability of finding a particular 5 digit number in a random sequence of 18 digits. We first use the f-function to calculate the number of possible ways it can occur:

formula.sample

The the probability is given by:

ratio

Here’s my faster algorithm

double f(int n, int m, int b)
{
    int nn = n; int sg = 1; int p = 0;
    int q = 0; int a = 1; double sum = 0;
    do {
        q = m-nn;
        p = q+a;
        sum += sg * Combin(p,q) * Math.Pow(b,q);
        sg = -sg;
        a++;
        nn += n;
    } while (m-nn >= 0);
    return sum;
}

”Combin(p,q)” is of course the combination-function – ”p over q”.

Annonser

The last invention that man need ever make

Let an ultraintelligent machine be defined as a machine that can far surpass all the
intellectual activities of any man however clever. Since the design of machines is one
of these intellectual activities, an ultraintelligent machine could design even better
machines; there would then unquestionably be an “intelligence explosion”, and the
intelligence of man would be left far behind. Thus the first ultraintelligent machine is
the last invention that man need ever make. (I. J. Good – 1965)

As quoted by David J Chalmers in his paper The Singularity: A Philosophical Analysis.