Find the probability that all triples of bits in a byte will not contain binary digits of only one type?

Question

Find the probability of the situation where we have 1 byte(8 bit) and there are no any 3 equal bits sequence in this byte. All values of the byte are equiprobable. I`ve tried to find the inverse probability, but i even do not know what is easier to perform. Also I made a binary tree of these byte and find out that probability is 26-27%, but it was bruteforce count. There are much more techniques that i've tried, but they won't help to find the solution.

To be clear, i`ll show the example:

$10101011$ - is ok

$10111000$ - is not ok, there are $111$ and $000$

Answer 1

You can solve this using a recurrence. Let $a_n$ be the number of admissible strings of $n$ bits that end in two equal bits, and $b_n$ the number of admissible strings of $n$ bits that end in two different bits, with initial values $a_2=b_2=2$. Then $a_{n+1}=b_n$ and $b_{n+1}=a_n+b_n$. Substituting the first equation into the second one yields $b_{n+1}=b_{n-1}+b_n$. We have $b_3=a_2+b_2=4$, so $b_2=2F_2$ and $b_3=2F_3$, where $F_k$ is the $k$-th Fibonacci number, and the recurrence is the one for the Fibonacci numbers, so for all $k\ge2$ we have $a_{k+1}=b_k=2F_k$.

In particular, $b_8=2F_8=2\cdot21=42$ and $a_8=2F_7=2\cdot 12=26$, for a total of $42+26=68$ admissible strings of $8$ bits, in agreement with your result $\frac{68}{256}=\frac{17}{64}\approx26.6\%$.

Answer 2

Consider $N$-bit strings without a triple. Suppose there are $A_N$ whose last two bits are the same, and $B_N$ whose last two bits are different.
Find a recursion for $A_N$ and $B_N$ in terms of each other.

Answer 3

Let $a_n$ be the number of admissible $n$-strings. Deleting the last run of equal bits from such a string either leaves an admissible string of length $n-1$ or an admissible string of length $n-2$. Conversely, to each such $(n-1)$-, resp. $(n-2)$-string we can add an additional run in exactly one way to obtain an admissible $n$-string.

It follows that $a_n=a_{n-1}+a_{n-2}$. Since $a_1=2$, $a_2=4$ we see that $a_n=2 F_{n+1}$, where $(F_n)_{n\geq0}=(0,1,1,2,3,\ldots)$ are the Fibonacci numbers. It follows that the probability $p$ in question is given by $$p={2F_9\over 2^8}={17\over 64}\ .$$