What is the probability of observing 5 consecutive 1s in a b

What is the probability of observing 5 consecutive 1\'s in a bit string of length 7

What is the probability of observing either 3 consecutive 0\'s and 5 consecutive 1\'s in a bit string of length 7

Solution

a) total number of possibilities in a bit string of length 7=2^7

number of possibilities in which there is 5 consecutive 1\'s=1111100,1111101,1111110,1111111,0111110,0111111,0011111,1011111

probabitility=8/2^7

b)

Let an be the number of bit-strings of length n with 3 consecutive zeros. Then

a_n=2a_n-1 +2^n-4a_n-4

because you can get such a string from a such a string of length n1 by putting a zero or a one at the end, or from a string of length n4 with no 3 consecutive zeros by tacking 1000 on at the end. Clearly a0=a1=a2=0 and a3=1, and then you can use the recursion to find a4=3, a5=8, a6=20, a7=47.

For bit-strings with 5 consecutive ones, the same logic gets you to

a_n=2a_n-1 +2^n-6a_n-6

a₅₌1,a₆=3 ,a₇ =8

Required possibilities=47+8=55 (0 common terms)

probability=55/2^7