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

Question

I'm trying to code a simple, sufficiently accurate filter for validating a piece of hardware in an RTL simulation. We're simulating the randomness inherent in a chip's flip-flops, by randomly initializing all the flip-flops in the design to either 0 or 1. This corresponds to the chip's flip-flops getting some random value during power-up. We're also randomizing the flops in the reset tree ( where reset tree has no feedback loops ), which means that you can get false glitching on your reset lines.

e.g.

                              |||
                              VVV                          Nth reset-tree flop
          +----+       +----+       +----+        /     /    +----+ 
reset_in  |    |  0    |    |  1    |    | 0     /     /     |    | reset_out
 -------->D    Q>----->D    Q>----->D    Q>---- / ... /   -->D    Q>----
          |    |       |    |       |    |      \     \      |    |
          |    |       |    |       |    |       \     \     |    |
          +^---+       +^---+       +^---+       /     /     +^---+
           |            |            |          /     /       |
clk  ------+------------+------------+---------/     /     ---+

You'll see a 0->1->0 which looks like a reset, but is really a glitch.

I want to build a filter that looks for a certain number of consecutive 1 values to determine whether the reset I just saw was the reset coming from the reset controller or a spurious reset.

I know this is statistics and maybe related to the Poisson distribution, but how do I determine the probability that any X consecutive bits in a set of N bits are 1?

P.S. Yes. I am aware of 4-val RTL simulation. We're doing that also, but some Verilog constructs don't have sufficient pessimism when propagating X's and Z's.

Answer 1

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 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

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 4

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 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],