What's the probability that X *consecutive* bits in an array of N bits is set to 1?

Answer 1

OK, here's what I found:

P = 1 - Q(X)

where

Q(X) = [1 - 1/2(Z)]/[(X + 1 - XZ) x 1/2 x Z^(X+1)]

where

Z = 1 + (1/2)(1/2)^X + (X+1)[(1/2)(1/2)^X]^2 + ...

The link with some of the math is here:

Math Forum

Answer 2

EDIT: The below doesn't answer the question, sorry... Comment clarified that the real problem is about the probability of x consecutive 1s out of n bits, not just the simple thing I assumed. Had a quick look at this: http://www.mathhelpforum.com/math-help/probability-statistics/64519-probability-consecutive-wins.html which may be what you are looking for - it seems to deal with working out the probability of a run of toin cosses out of a larger population of toin cosses, so sounds similar. But its late and I am tired so I haven't decoded the math :)

OBSOLETE: It sounds like you are basically dealing with binominal probability - see http://en.wikipedia.org/wiki/Binomial_probability.

I have to admit I haven't done the calculations for about 20 years, so somewhat rusty...

Basically, binominal allows you to "add together" the probability of an event occuring multiple times, where there is only two possible outcomes each time. Order is significant in your case so it should be as simple as multiplying the probabilites;
For 1 bit it is 50%
For 2 bits it is 50%^2 = 25%
For 3 bits it is 50%^3 = 12.5%

Look at it another way;
1 bit only has 2 possible combinations, one of which is all 1s = 50%
2 bits have 4 possible combinations (10, 01, 11, 00), only one of which is all 1s - so 25%
3 bit have 2^3 = 8 possible combinations, only one of which is all 1s, so 1/8 = 12.5%

So... probability of n bits all being 1 = 1/(2^n).

Answer 3

you can do a recursive program (python):

prob (x,n) gives your desired result

---

import math

def prob(x,n,i=0):
    if i == x: return 1
    if (x+i) > n: return 0
    t = .5 * prob(x,n-1,i+1) + .5 * prob(x,n-1,i)
    return t

Answer 4

If you want a quick test to see if a sequence of bits is random based on the longest streak of 1's, you can use the fact that the expected longest streak of 1's in N bits is Θ(log(N)).

Furthermore, the probability that the longest streak exceeds r*log₂(N) bits is at most 1/N^(r-1), and similarly the probability that the longest streak is less than log₂(N)/r bits is at most 1/N^(r-1).

These results are derived in the section on "Streaks" in the chapter on "Counting and Probability" in Introduction to Algorithms

Answer 5

My approach to this would be to define a FSA that accepts bit patterns of the correct type, and then simulate the pattern for each number of bits. i.e.

State state_map[] = {
    0 => { 0 -> 0; 1 -> 1; accepts = false },
    1 => { 0 -> 0; 1 -> 2; accepts = false },
    2 => { 0 -> 0; 1 -> 3; accepts = false },
    3 => { 0 -> 3; 1 -> 3; accepts = true }
};

state[t: 0, s: 0] = 1.0;
state[t: 0, s: 1] = 0.0;
state[t: 0, s: 2] = 0.0;
state[t: 0, s: 3] = 0.0;

for (t = 0; t < N; t++)
    for (s = 0; s<NUM_STATES; s++)
        state[t: t+1, s: state_map[s].0] += state[t, s] * .5
        state[t: t+1, s: state_map[s].1] += state[t, s] * .5

print "Probability: {0}", state[t: N, s: 3],