0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ @joriki, Thanks. Is everything alright now? $\endgroup$ – Fedurko Nikolaus Sep 17 '18 at 10:49
  • $\begingroup$ Yes, I think it's clear now. $\endgroup$ – joriki Sep 17 '18 at 10:51
3
$\begingroup$

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\%$.

$\endgroup$
  • 1
    $\begingroup$ Thanks, very usefull technique. $\endgroup$ – Fedurko Nikolaus Sep 17 '18 at 16:29
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}\ .$$

$\endgroup$

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.