0

I have a random binary string of N bits with N/2 bits are one and N/2 bits are zero and the bits are generated by coin tossing so they have entropy N. Now I feed the bits to a deterministic algorithm that generates psuedorandom permutations of these N bits with the restriction that for each permutation you are not allowed three consecutive bits with the same value ( you can have 1001 but not 10001 anywhere in the sequence). How many ways can N be arranged? And finally does each string generated have the same entropy as the original string?

William Hird
  • 41

2 Answers2

1

If you know that exactly $\frac N2$ bits are $1$ and $\frac N2$ bits are $0$ the string does not have entropy $N$. There are ${N \choose N/2}=\frac {N!}{((N/2)!)^2}\approx \frac {2^N}{\sqrt {\frac \pi 2 N}}$ such strings, so the entropy is about $N-\frac 12\log_2 N-\frac 12 (\log_2 \pi -1)$, not much of a reduction. Restricting to strings which do not have three in a row decreases the number of allowable strings, so the entropy is decreased. I don't see an easy way to impose both requirements (same number of $1$s and $0$s and no three in a row) simultaneously. The number of strings lacking three in a row satisfies the Fibonacci recurrence because an acceptable string of length $N$ can be an acceptable string of length $N-1$ to which you append the opposite bit to the last or an acceptable string of length $N-2$ to which you append two opposite bits. That costs you a factor $\log_2 1.618 \approx 0.694$ on your entropy.

Ross Millikan
  • 374,822
  • Why doesn't the original string have entropy N, why does the fact that you know the string happens to be balanced that it reduces the entropy? – William Hird Sep 03 '17 at 22:00
  • 1
    Because having it balanced reduces the number of strings. To have entropy $N$ you must be choosing between $2^N$ things, but there are not that many. It is a small reduction, just the factor in the denominator, but there are less of them. For example, if $N=4$ there are only $6$ balanced strings out of $16$ total strings, so the entropy is only $\log_2 6 \approx 2.58$ bits. – Ross Millikan Sep 04 '17 at 04:52
0

For the count, here's a recursion, implemented in Maple . . .

enter image description here

quasi
  • 58,772
  • I'm looking for a answer that is a function of N. How did you come up with an integer, I never gave you a value for N. – William Hird Sep 03 '17 at 22:16
  • A closed form is unlikely. A recursion allows calculation for a given value of $N$. The output is just a demo of the recursion for even values of $N$ with $2 \le N \le 20$, and also, just for show, for $N=100$. – quasi Sep 03 '17 at 22:21
  • OK, so this big number (looks like the national debt !) is for N=100, is this with the restriction of no three consecutive bits can be the same? – William Hird Sep 03 '17 at 22:36
  • Yes. For an even positive integer $n$, $f(n)$ is the number of binary sequences of length $n$ with equally many ones and zeros, and such that no $3$ consecutive terms are equal. I can do $f(1000)$ just as easily -- takes about 1 sec, but it's really big. – quasi Sep 03 '17 at 22:46
  • My N will be 128, thanks for running the numbers. – William Hird Sep 03 '17 at 22:55
  • $f(128)=135650433434209670338003770$. – quasi Sep 03 '17 at 22:57
  • Just for giggles, what would N of 256 be, I might need to establish an upper bound later for my hash function. Thanks again ! – William Hird Sep 03 '17 at 23:48
  • $f(256)=54647851958813382527641469896838773438304466763306152$. – quasi Sep 03 '17 at 23:53