4
$\begingroup$

Just what the title says, I'm trying to determine the probability of a randomly chosen bit string of length $8$, not containing $2$ consecutive $0$'s. I've determined the total number of possible bit strings of length $8$ with $2^8$, but after that I become confused as to what approach I should take.

I've counted the number of strings that containing $2$ consecutive $0$'s at every position in the string ex:

$$00111111\\ 10011111\\ 11001111\\ 11100111\\ 11110011\\ 11111001\\ 11111100$$

But I'm not sure how to count the bit strings left that are NOT all $1$'s in every other position, because I'm basically just counting how many are bitstrings of length $6$ do not contain $2$ consecutive $0$'s. This has led me to the conclusion that I likely need to utilize a recurrence relation, but I am unsure of how to proceed from here.

Any help is much appreciated, thanks.

$\endgroup$
  • 1
    $\begingroup$ I assume $2$ consecutive $0$'s means at least $2$. You are right, it is easier to count the complement. If $a_n$ is the number of bit strings of length $n$ where no two consecutive $0$'s occur, show that $a_n=a_{n-1}+a_{n-2}$. The $a_n$ will turn out to be Fibonacci numbers. (It is a good idea as a preliminary step to find $a_0,a_1,a_2,a_3$ and maybe a few others by explicit listing.) $\endgroup$ – André Nicolas Apr 25 '15 at 22:00
  • $\begingroup$ For each of the seven strings that you have shown (with 2 consecutive zeros, and ones in all other positions), there are 6 ones. However, if you changed any of those ones to zeros, you would still have 2 consecutive zeros. Thus, you have 6 bits of freedom, or 2^6 variations for each of your seven strings. Naively, this would add up to 7 * 2 ^ 6 = 448. Unfortunately, this method double-counts some solutions, e.g. '00011111' is a variation of your first two strings. If you can figure out what to subtract from 448 to account for these double solutions, you will have the answer. $\endgroup$ – Jeff Irwin Apr 25 '15 at 22:02
  • $\begingroup$ The irony of me posting my alternate answer below, is that as I was double checking my work after posting, curious if anyone had made the connection I had, I came across this article which details both approaches used in the answers below and shows the identity as well. $\endgroup$ – JMoravitz Apr 26 '15 at 0:15
3
$\begingroup$

As Farnight and Andre noted, the number of sequences which don't contain consecutive zeroes will turn out to be Fibonacci numbers. Here is an alternate approach which yields a nice combinatorial identity for Fibonacci numbers.

Suppose we are looking at length $n$ binary sequences of $0$'s and $1$'s. Instead of thinking of it as $0$'s and $1$'s however, imagine it as $[\color{blue}{01}]$'s and $\color{red}{1}$'s with a possible $0$ at the far right. In other words, imagine we glued a 1 to the right of every 0 in order to forcibly avoid having two 0's in a row.

Either the furthest right entry in the sequence will be a 1 or a 0.

  • First case: Furthest right entry is a 1 (either a part of a $\color{blue}{01}$ or a $\color{red}{1}$), E.g. $\underline{\color{blue}{01}}~\underline{\color{red}{1}}~\underline{\color{red}{1}}~\underline{\color{blue}{01}}~\underline{\color{blue}{01}}$

There can be anywhere from zero to $\lfloor\frac{n}{2}\rfloor$ number of $[\color{blue}{01}]$'s. Let $k$ be the number of $[\color{blue}{01}]$'s. Then there are $n-2k$ copies of $\color{red}{1}$'s to place. Thus, for a specific $k$, we have a total of $k+n-2k=n-k$ spaces in which we either place a $\color{blue}{01}$ or a $\color{red}{1}$ for a total of $\binom{n-k}{k}$. Ranging over all possible $k$, we find that there are $\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}$ possible sequences in the first case.

  • Second case: Furthest right entry is a $0$. E.g. $\underline{\color{red}{1}}~\underline{\color{blue}{01}}~\underline{\color{red}{1}}~\underline{\color{red}{1}}~\underline{\color{red}{1}}~\underline{\color{red}{1}}~\underline{0}$

There can be anywhere from zero to $\lfloor\frac{n-1}{2}\rfloor$ number of $[\color{blue}{01}]$'s. Let $k$ again be the total number of $[\color{blue}{01}]$'s. Then there are $n-1-2k$ copies of $\color{red}{1}$'s to place. Thus for a specific $k$, we have a total of $k+n-1-2k=n-1-k$ spaces in which we either place a $\color{blue}{01}$ or a $\color{red}{1}$ for a total of $\binom{n-1-k}{k}$ possibilities. Ranging over all $k$, we find there are $\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$ sequences in the second case.

Thus combining the cases, we have a total of $\sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$.

Noting that this answers the same question in a different form than the other answers, it gives us the identity for $n\geq 0$:

$F_{n+2} = \sum\limits_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-k}{k}$


For your specific example of length 8 binary sequences, my form gives:

$$\sum\limits_{k=0}^{\lfloor\frac{8}{2}\rfloor}\binom{8-k}{k}+\sum\limits_{k=0}^{\lfloor\frac{8-1}{2}\rfloor}\binom{8-1-k}{k}\\ =\sum\limits_{k=0}^{4}\binom{8-k}{k}+\sum\limits_{k=0}^{3}\binom{7-k}{k}\\ =\binom{8}{0}+\binom{7}{1}+\binom{6}{2}+\binom{5}{3}+\binom{4}{4}+\binom{7}{0}+\binom{6}{1}+\binom{5}{2}+\binom{4}{3}\\ =1+7+15+10+1+1+6+10+4= 55$$

and $55$ is the $10^{th}$ Fibonacci number.

(note also, I count the Fibonacci sequence with $F_0=0, F_1=1, F_2=1,F_3=2,\dots$ whereas it seems Farnight above me counts $F_0=1,F_1=1,F_2=2,\dots$.)


A much cleaner approach which yields the same answer:

In a binary sequence of length $n$ without, there will be between $0$ and $\lfloor\frac{n}{2}\rfloor$ zeroes. Supposing that there are $k$ zeroes, then there are $n-k$ ones. Set up $n-k$ ones on a line. There are then $n-k+1$ spaces between or to the far left or right of the ones in which a zero may be placed. Pick $k$ of them to be occupied with a zero.

Ranging over all values of $k$, you get $\sum\limits_{k=0}^{\lfloor \frac{n}{2}\rfloor} \binom{n-k+1}{2}$, which again equals the same as the other answers. For $n=8$ you have $\sum\limits_{k=0}^4\binom{9-k}{k}=\binom{9}{0}+\binom{8}{1}+\binom{7}{2}+\binom{6}{3}+\binom{5}{4} = 1+8+21+20+5 = 55$


Of course, to complete the problem, note the numbers and formulae we came up with were counting how many sequences did not have consecutive zeroes. To count how many sequences do have consecutive zeroes, apply inclusion-exclusion. There are $2^n$ different length-$n$ binary sequences, so there are $2^n-F_{n+2}$ sequences which do have consecutive zeroes (or depending on how you define the starting values for the Fibonacci sequence, $2^n-F_{n+1}$). In our current example, there are then $2^8-55=256-55=201$.

To find the probability, take that number and divide by the size of the sample space, in our case $2^n$. Hence the probability for our example is $\frac{201}{256}$.

$\endgroup$
  • $\begingroup$ So, I follow your solution and the expected result. However, note that we calculated the number of bit strings that do not contain 2 consecutive 0's. Remember, our goal is to find the probability of picking a bit string with no 2 consecutive 0's. Thus, the final probability will be 55/256 or ~21%. Nothing actually wrong with your math obviously, you just switched the probabilities calculated for, which is completely understandable considering how much of a headache this problem is. $\endgroup$ – Theo Apr 27 '15 at 21:48
  • $\begingroup$ @user234442 ah, I see now that the title and body say two different things. I gave the answer I did based on the line in the body "I'm trying to determine the probability of a randomly chosen bit string of length 8 containing 2 consecutive 0's." $\endgroup$ – JMoravitz Apr 27 '15 at 22:16
  • $\begingroup$ Ah, my bad! I'll go ahead and fix that language. I thought that might be the issue initially, but only checked the question title. Also, thank you for your help it's much appreciated!! If you're hungry for another problem, the extra credit problem our professor has given us is posted here: math.stackexchange.com/questions/1255030/… Thanks again! $\endgroup$ – Theo Apr 27 '15 at 22:34
3
$\begingroup$

Let $C_n$ be the number of $n$ length bit strings that don't contain two consecutive zeros. If we have one of length $n+2$ satisfying this condition, then if the first bit is $1$, the rest must not have any consecutive zeros ($C_{n+1}$ possibilities). If it is $0$, then the second one is $1$ and the rest must satisfy that same condition ($C_{n}$). So $C_{n+2}=C_{n+1}+C_n$ ; $C_1=2$ ; $C_2=3$.

$$C_n=F_{n+1}$$

Where $(F_n)_{n\in \Bbb N}$ is the Fibonacci sequence

$\endgroup$
2
$\begingroup$

I would like to contribute an answer which is more of a dynamic programming approach.

  • Let $a_i$ denote the number of bit-strings with length $i$ which end in $1$.

  • Let $b_i$ denote the number of bit-strings with length $i$ which end in $0$.

Now, we want a string with no two consecutive zeros.
So, for the string of length ($i+1$), we can append $0$ or $1$ to a string ending in $1$.
But we can append only $1$ to a string ending in $0$.
This creates the recurrence relation as follows:
\begin{cases} a_{i+1}& = a_{i}+b_{i}\\ b_{i+1}& = a_{i} \end{cases} Base cases:
$a_1 = 1$, $b_1 = 1$. (String of length $1$: $0$ or $1$)

$a_2 = a_1 + b_1 = 1 + 1 = 2$
$b_2 = a_1 = 1$

$a_3 = a_2 + b_2 = 3$
$b_3 = a_2 = 2$

Similarly,
$a_4 = $5, $b_4 = 3$
$a_5 = $8, $b_5 = 5$
$a_6 = $13, $b_6 = 8$
$a_7 = $21, $b_7 = 13$
$a_8 = $34, $b_8 = 21$

Hence the total number of strings with no consecutive zeros is
$a_8 + b_8 = 34 + 21 = 55$.

The total number of possibilities $=2^8=256$.
Total favourable cases $=256-55 = 201$.
Hence, probability $= 201/256$.

$\endgroup$
  • $\begingroup$ As an answer this needs a bit more meat. In between your base cases you start off with $a_1$, $b_1$, but don't quite explain how you arrive at $a_8=34$, $b_8=21$, or at least I can't immediately see that you are correct. If so it's a nice answer, just needs expounding on. $\endgroup$ – Daniel Buck Sep 18 '16 at 14:39
  • $\begingroup$ Thank you for the feedback! I've included the necessary steps. $\endgroup$ – Rishiraj Surti Sep 18 '16 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.