probability of a consecutive sequence

[Mintguy]

I need a mathematician.

If I have a random sequence of bits being received from a datastream, how can I determine the probability that after n bits I will have received at least 1 sequence of r consecutive 1s?

By analysis I can determine that after 3 bits are received the probability of getting 3 consecutive 1s is 1/8, after 4 bits it's 3/16 and after 5 bits it's 8/32.

What is the general formula?

Regards

Mintguy

[Alexey B]

The number of possible favourable outcomes in n bits is n-r+1.
The number of possible outcomes is 2^n.
Therefore, the probablity is (n-r+1)/(2^n).

Also, I think your analysis is skewed because there are only two ways you can get 3 consecutive bits in a 4 bit sequence, 0111 and 1110.

[Mintguy]

No.

After 4 bits there are three possibilities .. 0111, 1110 and 1111.

After 5 bits ... eight possibilities .. 00111, 01110, 01111, 10111, 11100, 11101, 11110 and 11111.


Your formula suggests, 2/16 for the former and 3/32. Which I judge to be correct for a single sequence of 3 set bits in isolation. But not for the more general case for which I am enquiring.

[Alexey B]

Oh I see, that is a great deal harder. Not impossible though, just give me a minute.

[Alexey B]

I give up. This problem is too hard. The following code can find the probabilty, but it does it by actually calculating all the possible combinations of n elements and the number of occurences of r elements in a row. It can be a solution if you only need to calculate the probability once, but otherwise, it is fairly useless. I'm sorry I could not be of any more help.

const int N = 8;
const int R = 3;
bool field[1<<N][N];
int a, b;
int nFound = 0, count;

// fill the field with all possible combinations of N bits
for (a = 0; a < N; a++)
{
	for (b = 0; b < 1 << N; b++)
	{
		field[b][a] = (b / (1 << a)) % ((1 << N) / (1 << a)) % 2 == 0;
	}
}
// count the number of consecutive elements
for (a = 0; a < 1 << N; a++)
{
	count = 0;
	for (b = 0; b < N; b++)
	{
		if (field[a][b] == true)
		{
			count++;
			if (count >= R)
			{
				nFound++;
				break;
			}
		}
		else
		{
			count = 0;
		}
	}
}
// probability = nFound / 2^N

The code has being compiled - it works.

[Mintguy]

I've written similar code myself for this problem. For large n (and n can be very large indeed) it takes too long to go through the combinations. I used the resultant values to try to derive a function. The function is recursive because f[r](n) references f[r](n-1) and involves it exponential growth and a fibonacci series, but I can't get it right, it keeps breaking down for higher values.

The problem as described in the first post is a simplification of the real problem. I'm looking for a specific pattern of bits but it might just aswell be all 1s.

[Mintguy]

Bump... no answer yet

[jfaust]

I went the opposite way as Alexey B.

This is wrong, but here it is:

The number of possible favourable outcomes in n bits is (n-r+1)*2(n-r).
The number of possible outcomes is 2^n.
Therefore, the probablity is (n-r+1)*2^(n-r)/(2^n).

2^(n-r) comes in because that's the number of bits left in which we don't care what they are. The problem is that it counts 1111 twice when n = 4 and r = 3.

The real probability is between Alexey's on the low end and mine on the high end. Now, I can't figure out how to calculate the number of times a string is counted twice by mine.

Interesting problem.

Jeff

[jwbarton]

Another possible way to approach this is the compute the probability of the opposite event - receiving n bits without having any sequence of r bits in a row set. Then you can get the desired result by subtracting this probability from 1.

One way I could think of to calculate this probability is to try to count how many valid combinations are added each time that you add a bit to the sequence.

For n < r: count(n) = 2^n
For n = r: count(n) = 2^n - 1
For r < n <= 2r: count(n) = count(n-1)*2 - 2^(n-r-1)
For 2r < n: count(n) = count(n-1)*2 - count(n-r-1)

Basically, I assume that the count of possibilities doubles each time that you add a bit minus the count of current bit patterns which end with (r-1) bits set.

I am not sure that I got the last range correct - it seems OK, but I might have messed it up. I also am not sure how you would convert these to a single formula.

Once you have the count, it is easy to calculate the probability that you want:

p(n) = 1 - count(n) / (2^n)

Best regards,
John