# Exponential/permutation combinatorics problem for leisure

I've been trying to solve the problem below for over an hour doing everything but writing it out by hand. I've tried looking for patterns in strings of lengths $2, 3, 4,$ and $5$ which have probabilities $1/4, 3/8, 8/16,$ and $19/32$, respectively, of having two or more consecutive $1$s.

I'm more interested in the formula and theory behind solving the problem than the answer itself. I've searched online for permutation and probability problems without success.

Problem:

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?

Problem is from the app below: https://play.google.com/store/apps/details?id=atorch.statspuzzles

• Hint: each position in the string can has two different 'choices' (either it's $0$ or $1$). So, for example, there are $2 \times 2 = 4$ choices for a two-digit string. Khan academy gives a decent introductory account here: khanacademy.org/math/precalculus/prob-comb Apr 7 '17 at 14:14
• Thank you. I know how to get the total number of permutations. 2^n where n is the length of the string. What I am having trouble with is the formula for calculating the number of permutations that will have two or more consecutive 1s. Apr 7 '17 at 14:22
• You can solve it by markov chains with the approach on my old answer: math.stackexchange.com/questions/2216650/… _ Just sum the last two states for ${\bf P}^8{\bf v}$ _ I can expand later if you want, but I'm in a hurry now. Apr 7 '17 at 14:54

Let's try to solve the opposite problem first: counting the number of bitstrings with no consecutive ones.

Let $A_n$ be the set of bit strings of length $n$ with no consecutive $1$'s and let $a_n = |A_n|$, i.e., $a_n$ is the number of bit strings of length $n$ with no consecutive $1$'s. Clearly, $a_1 = 2, a_2 = 3$.

Consider a bit string in $A_n$. Then it can be formed in the following ways:

1. $0$ followed by any bit string in $A_{n-1}$.
2. $10$ followed by any bit string in $A_{n-2}$.

Thus, it follows that: $$a_n = a_{n-1} + a_{n-2}.$$

Using standard techniques for solving recurrence relations, you should be able to find a formula for $a_n$. If we let $b_n$ be the number of bit strings that have consecutive $1$'s, then since there are a total of $2^n$ bitstrings of length $n$, then $a_n+b_n = 2^n \implies b_n = 2^n-a_n$. Thus, the probability of getting a bitstring with consecutive $1$'s is:

$$\frac{2^n-a_n}{2^n} = 1-\frac{a_n}{2^n}.$$