Binary Probability Question / Riddle

Question

My friend and I are working through a collection of probability questions to practice. We came across the following question. After some work we were able to find two methods of solving the problem, but both of the solutions were pretty clunky.

Based on the source, we believe there is a relatively straight forward and elegant solution to this question, but we can't find it. What is it?

For the purposes of this puzzle, a "string" means a sequences of zeros and ones, e.g. 1011.

Consider all the different strings of length eight — a good first step would be to figure out how many of these exist.

If you pick a length-eight string uniformly at random, what's the probability that it contains two (or more) consecutive 1s?

I will post our two solutions in an answer below but not select it as the actual answer.

Answer 1

Your second approach can be improved. In the first case, a string begins with $1$, and the possible choices for the remaining $7$ bits can enumerated as you have already done, thus $21$ strings that begin with $1$ with no two consecutive $1$s. In the second case, a string begins with $0$, and you must count the ways to arrange $A$ and $B$ to form an $8$-bit string. There are: $$\binom{8}{0} = 1 \quad \text{way to choose no } B \\ \binom{7}{1} = 7 \quad \text{ways to choose one } B \\ \binom{6}{2} = 15 \quad \text{ways to choose two } B \text{s} \\ \binom{5}{3} = 10 \quad \text{ways to choose three } B \text{s, and} \\ \binom{4}{4} = 1 \quad \text{way to choose four } B \text{s.}$$ In fact, you can see that the number of $n$-bit strings that can be created is simply $$S(n) = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}.$$ So you can also get the result for $7$-bit strings by computing $$\binom{7}{0} + \binom{6}{1} + \binom{5}{2} + \binom{4}{3} = 21.$$ For the $8$-bit strings, you get $34$, thus the total number of such strings is $55$, and the complement is simply $256-55 = 201$, and the desired probability is $$\frac{201}{256}$$ as claimed, and we can immediately generalize to compute the total number of $n$-bit strings that contain at least one pair of consecutive $1$s as $$P(n) = 2^n - S(n) - S(n-1)$$ where $S$ is the sum given above.

---

In case the enumeration via binomial coefficients is not clear, let's break it down by looking at a specific example. Say you have a $13$-bit string, and you want to use $3$ pairs of bits of type $B$, which means you'd need to use $7$ single bits of type $A$, and you want to make a $10$-letter string of $A$s and $B$s from these. Clearly, you can choose $\binom{10}{3}$ distinct positions in the string to place the $B$s.

In general, if you use $k$ pairs, that takes $2k$ bits, so you can only use $n - 2k$ bits of type $A$, and in total, you'd have a lettered string of length $n - 2k + k = n-k$ made of $A$ and $B$s. So now you have a string of $n-k$ letters, for which there are $\binom{n-k}{k}$ ways to choose the positions of the $B$s.

Answer 2

Inelegant Solution 1

$$ \begin{align} P = \frac{1}4 + \frac{3}4\times \left( \frac{1}6 + \frac{5}6\times \left( \frac{2}{10}+\frac{8}{10}\times \left( \frac{3}{16}+\frac{13}{16}\times \left( \frac{5}{26} + \frac{21} {26}\times \left(\frac{8}{42} + \frac{34}{42} \times \left( \frac{13}{68} \right) \right)\right)\right)\right)\right) \end{align} $$

This gives

$$ P = 0.78515625 $$

We built this equation one section at a time, first considering a string of length two, then of length three, then of length four, etc. At first we assumed every section would have the same co-efficient (1/4) but soon realize that there was a monty-hall-esque selection thing going on, and had to figure out the coefficients one at a time.

Interestingly: the coefficients of each section (1/4, 1/6, 2/10, 3/16, etc.) are Fibonacci sequences in the numerator and denominator. Once we saw that, it was a little easier to quickly figure out the answer.

So, our first equation was:

$$ P(Length_2) = \frac{1}{4} $$ Then we did a weighted averages function with the probabilities for the string starting in the second slot: $$ P(Length_3) = \frac{1}{4} + \frac{3}{4} \times ( \frac{1}6 ) ) $$

And then just kept expanding that until we got all eight positions considered:

$$ P(Length_4) = \frac{1}{4} + \frac{3}{4} \times ( \frac{1}6 + \frac{5}6(\frac{2}{10} ) ) $$

etc.

Inelegant Solution 2

Let's count the negative cases and then subtract that number from the total number of possible permutations (i.e. 256).

Define A = 0 and B = 01

With these definitions, we can count the permutation of a string composed of A's and B's and only be counting "failed" matches.

First, imagine all strings of A and B where the binary length is 7.

AAAAAAA = 1 permutation
AAAAAB = 6 Permutations
AAABB = 10 Permutations
ABBB = 4 Permutations

Since the strings are only of length 7, we can see that we can put either a 1 or a 0 at the beginning of each string, and given the definitions of A and B, all of those will be negative results.

Therefore, we have identified ( 1 + 6 + 10 + 4 ) * 2 = 42 negative results.

However, we missed a set of cases. Negative-result strings in this form: 010XXXXX are not counted.

We manually brute forced the number of negative-result permutations for the XXXXX above:

1.  00000
2.  00001
3.  00010
4.  00100
5.  01000
6.  10000
7.  00101
8.  01001
9.  01010
10. 10001
11. 10010
12. 10100
13. 10101

42 + 13 = 55 negative-result cases.

Therefore, the answer is (256-55)/256, or 201 / 256.

$$ P = 201/256\\ P = .78515625 $$

Answer 3

how about to divide & conquer? sum the options for any amounts of 1's in the strings, and then do the rest of the math: i'll notate $A_i$ as the strings who has i-sh 1's and with at least consecutive of two 1's in it:

$|A_8|=1$ which is obvious. $|A_7|={8 \choose 1}$, cause its to pick the place for the only 0's in the sequence. $|A_6|={8 \choose 2}$, for the same reason. $|A_5|={8 \choose 3}$. $|A_4|={8 \choose 4} - 2$, cause there is only two arrangements s.t there is no at least two consecutive 1's in it: 10101010 and 01010101. $|A_3|$ is a bit more tricky but you can understand the idea of how to manage it. $|A_2|={7 \choose 1}$ cause you have only $7$ places for the left 1's, and the second must come next to it.

$|A_1|=0$ and $|A_0|=0$ also cause of obvious reasons.

all is left to do is to calculate $$P= \frac {\sum_{i=0}^8 |A_i|}{2^8=256}$$