Binary Strings

Thanks for a fun little problem and a Fibonacci surprise. I Explain why at the end, but the number of strings that don't contain any consecutive 1s forms a sequence of Fibonacci numbers. For strings of length 1 to 8 respectively, we have 2, 3, 5, 8, 13, 21, 34, 55 that don't contain any consecutive 1s. This means there are $2^8 - 55 = 256 - 55 = 201$ 8-digit strings that contain 2 or more consecutive 1s.

Hence the probability required is $\frac {201} {256} = 0.785...$

Explanation

For a string of length 1 there are 2 sequences that do not contain consecutive 1s: $\color{#3D99F6}0\color{#333333}, \color{#3D99F6}1$ .

For a string of length 2 there are 3 sequences that do not contain consecutive 1s: $\color{#D61F06}00\color{#333333},\color{#D61F06}01\color{#333333},\color{#D61F06}10\color{#333333}$ .

Now for the clever bit. We can append "0" to the front of each string of length 2 and append "10" to each string of length 1. Combining these gives all the strings of length 3 that do not contain consecutive 1s:

$0\color{#D61F06}00\color{#333333}\\ 0\color{#D61F06}01\color{#333333}\\ 0\color{#D61F06}10\color{#333333}\\ 10\color{#3D99F6}0\color{#333333}\\ 10\color{#3D99F6}1\color{#333333}$

More generally, we can get a string of length $n$ by appending "0" to the front of each string of length $n-1$ that satisfies the conditions and appending "10" to each string of length $n - 2$ that satisfies the conditions. Conversely, for each string of length $n$ , if it starts with a "0", then we can drop it and get a string of length $n - 1$ that satisfies the conditions; if it starts with a "1", then the next number is not a "1" hence it is a "0", then dropping these first two digits gets us a string of length $n - 2$ that satisfies the conditions.

Continuing in this way, it becomes clear that, as we increase the length of the string, the number of strings that do not contain consecutive 1s form a Fibonacci sequence.

Let $a_{n}$ be the no. of binary strings of length n that contains no consecutive 1's. Let among these strings $b_{n}$ be the number of strings ending with 0 and $c_{n}$ be number of those that ends with 1. Clearly $b_{n+1} = b_{n} + c_{n}$ , since in order to have a string of length $n+1$ ending with 0 and having no consequtive 1's, we may append 0 to any string of length $n$ . Again $c_{n+1} = b_{n}$ , since only way to create a string of length $n+1$ maintaining the required condition and ending in 1 is to append 1 to a string of length $n$ that ends with 0. Noting that $a_{n} = b_{n} + c_{n}$ , and by performing some algebraic manipulation of the recursions obtained we obtain $a_{n} = a_{n-1} +a_{n-2}$ . Also note that $a_{1} = 2$ and $a_{2} = 3.$ Hence we obtain $a_{8} = 55$ . Thus there are 55 total binary strings of length 8 that do not contain any consecutive 1's. There are a total of $2^8=256$ binary strings of length eight. Hence total no. of strings having atleast two consecutive 1's is $256-55= 201$ . Thus the required probability is $201/256 = 0.785$

Here is a ``brain-dead" solution that does not require any thinking on our part.

Let $u(n,0)$ denote the number of binary sequences of length $n$ that does not contain two consecutive ones and ends with $0$ . Similarly, define $u(n,1)$ to be the number of binary sequences of length $n$ that does not contain two consecutive ones and ends with a $1$ . Then we have the following recursions $u(n+1,0)= u(n,0) + u(n,1), \hspace{5pt} \textrm{and} \hspace{5pt} u(n+1,1)= u (n,0)$ In matrix notation, we can write $\vec{u}(n+1) = \begin{pmatrix} 1 && 1\\ 1 && 0 \end{pmatrix}\vec{u}(n)$ where $\vec{u}(n)= \begin{pmatrix} u(n,0) \\ u(n,1) \end{pmatrix}$ Iterating the equation above, we conclude that $\vec{u}(n)= \begin{pmatrix} 1 && 1\\ 1 && 0 \end{pmatrix}^{n-1}\vec{u}(1)= \begin{pmatrix} 1 && 1\\ 1 && 0 \end{pmatrix}^{n-1}\begin{pmatrix} 1\\ 1 \end{pmatrix}$ From which, we compute $u(8,0)= 34, u(8,1)=21$ . Thus the total number of binary sequences of length $8$ , not containing conseuctive $1$ s is $34+21=55$ . Thus, the required probability is $1- \frac{55}{2^8}= 0.7852$ .

Use the principle of inclusion and exclusion.

The number of binary strings which contain 2 or more consecutive 1's = Total combinations(2^8) - number of strings which do not contain any consecutive 1's

Number of strings which contain no consecutive 1's:

A Maximum of Four 1's are possible(PigeonHole principle) and will have to be place in the gaps of the 0s. This can be done in 5 ways. (10101010, 01010101, 10010101,10100101,10101001 )

Similarly Three 1's and Five 0's can be arranged in 20 ways.

Two 1's in 21 ways.

One 1's can be arranged in 8 ways

Zero 1's can be arranged in 1 way(00000000)

There total number of strings with no consecutive 1's = 5 + 20 + 21 + 8 + 1 = 55

The number of strings that have 2 or more consecutive 1's = 2^8 - 55 = 201

Probability that the selected string has 2 or more consecutive 1's = (201/256) = 0.785