3
$\begingroup$

Can you have a process that generates a binary sequence with high compression rate (low entropy) but impossible to predict next symbol?

'impossible to predict' - sequence cannot be predicted theoretically. But I was also asking about the real life example (no polynomial algorithm).

Improve this question
$\endgroup$
  • $\begingroup$ Please formally define "impossible to predict". As you can see, your unclear definition results in two totally different answers. orip's answer assumes there is (possibly) no polynomial algorithm that can predict the sequence, while D.W.'s answer assumes the sequence cannot be predicted theoretically. $\endgroup$ – xskxzr Sep 14 '19 at 3:42
2
$\begingroup$

No. Let $x_1,x_2,\dots,x_n$ be the bits of the binary sequence.

Suppose $\Pr[x_{i+1} | x_1,\dots,x_i] = 1/2$ for all $i$. Then it is impossible to predict the next bit; however, it is also easy to see that $x_1,\dots,x_n$ is uniformly distributed on $\{0,1\}^n$, so has entropy $n$ (high entropy; no compression possible).

Alternatively, suppose $\Pr[x_{i+1} | x_1,\dots,x_i] \ne 1/2$ for some $i$. Then it is possible to predict the next bit better than chance.

Those are the only two possible cases. In every case, either the next bit is predictable, or you can't compress.

This assumes you are talking about what is possible with infinite computing power (which isn't realistic, but is what is typically assumed in information theory).

Improve this answer
$\endgroup$
3
$\begingroup$

Yes. A cryptographic stream cipher can generate an incredibly long string (e.g. ChaCha20 can generate $256 \times 2^{128}$ bits) from a single small key (e.g. 256 bits).

If you do not know the key that was used this stream is impossible to predict.

Improve this answer
$\endgroup$
  • $\begingroup$ will it be highly compressible? I mean low entropy. $\endgroup$ – Oleg Dats Sep 12 '19 at 9:50
  • 1
    $\begingroup$ @OlegDats Yes, the entropy is still just 256 bits - you can generate everything from just the key. $\endgroup$ – orlp Sep 12 '19 at 10:14
  • $\begingroup$ 256 bits + lenght of the code of ChaCha20 algorithm? $\endgroup$ – Oleg Dats Sep 12 '19 at 10:26
  • $\begingroup$ @OlegDats That depends on your definition of entropy, but in traditional Kolmogorov complexity that would be an upper bound for any implementation of ChaCha20, yes. It is unknown what the smallest size implementation of ChaCha20 is though. In cryptography we go by Kerckhoffs's principle and only count the bits of the secret key as our entropy. $\endgroup$ – orlp Sep 12 '19 at 10:29
  • 1
    $\begingroup$ @gnasher729 ChaCha20 is not invertible, so the first 256 bits of output probably does not give enough information even in the ideal case. And how do you define 'possible to predict'? If your prediction takes longer than the heat death of the universe, is that 'possible'? $\endgroup$ – orlp Sep 13 '19 at 10:44
1
$\begingroup$

The accepted answer is plainly wrong.

It's not really low predictability. After the first 256 bits, the rest is perfectly predictable, it is just very hard. It's not impossible to predict. So the answer is wrong.

And the argument doesn't make sense. It's very hard to predict (but not impossible) without knowing the key. But it is equally very hard (but not impossible) to compress without knowing the key.

Improve this answer
$\endgroup$
  • $\begingroup$ Maybe you are right, it is impossible to compress without knowing the key. (I will de accept the current answer) $\endgroup$ – Oleg Dats Sep 13 '19 at 7:47
  • $\begingroup$ This does not answer the question. It is better to be a long comment. $\endgroup$ – xskxzr Sep 14 '19 at 3:38

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.