Can a transform lower the Kolmogorov entropy of a true random stream and then restore that stream with out loss.

If not true then this means a transform can not raise or lower the entropy.


closed as unclear what you're asking by Ilmari Karonen, AleksanderRas, kelalaka, yyyyyyy, tylo Aug 12 at 15:51

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What does "an algorithm can not alter a true random stream to a lower entropy" mean? An algorithm can transform any stream to one that puts out all zeroes. $\endgroup$ – bmm6o Aug 6 at 16:36
  • $\begingroup$ I find it more practical (and it matches other branches of science) to think of it as Kolmogorov/algorithmic entropy. That allows you to take 'entropy' measurements at various points in the trail of functions. This paradigm is important when talking about TRNGs, especially wrt what goes on inside them. $\endgroup$ – Paul Uszak Aug 6 at 18:04
  • 2
    $\begingroup$ And if you're using an entropic argument for the non compressibility of native information, then you certainly need to use the Kolmogorov entropy nomenclature. $\endgroup$ – Paul Uszak Aug 6 at 19:23
  • 1
    $\begingroup$ There are three statements here, some contradictory. What's the question exactly? $\endgroup$ – Paul Uszak Aug 6 at 21:11
  • $\begingroup$ Can a transform lower the Kolmogorov entropy of a true random stream and then restore that stream with out loss. $\endgroup$ – Jon Hutton Aug 7 at 1:00

Kolmogorov complexity($\operatorname{K}$) is the lowest bound measure of the native information content of a thing. There's no smaller way to completely describe the thing, and the fractal box on the RHS of the linked page is a very good example. Taken per unit time, it's the rate that new native information is created. And it has the property that it can travel upstream through all connected functions to the head of where the information is originally created. In cryptography, that would be from some physical mechanism.

Now imagine a true source $S$, and reductive and expansive functions $F_R$ and $F_E$. Say $F_R$ replaces all even byte values with "42". $F_R(S)$ would cause $ \operatorname{K}(F_R(S)) $ rate to reduce significantly as evens' information is lost and the stream becomes simpler to describe. Probably by ~50%. If you also measured Shannon entropy rate at this point, knowing nothing else, it would be ~50% of the original rate of 100%. The stream would also be compressible due to there being excess of {odd, 42}, {42, odd} and {42, ..., 42} tuples.

Then we do $F_E(R_F(S))$, where $F_E$ is an encryption under some key $k$. As $\frac{|k|}{|S|} \to 0$ in the long run, nothing has really been added. Although now the stream has lost it's apparent redundancy, and has become computationally indistinguishable from truly random. The abundance of 42s has been confused and diffused away. If we again measure the Shannon entropy at this very point a priori, it has expanded back to 100%. And it has become incompressible again. It's been disguised by $F_E$ if you will. Yet since we know a posteriori that nothing was added, $\operatorname{K}(F_E(R_F(S)))$ rate still equals ~50%.

Using NIST parlance, Kolmogorov complexity rate depends on the narrowest/lowest internal 'width' or rate within the holistic system of functions. Whilst Shannon entropy rate can be spot measured at any point to give widely different values for the same Kolmogorov rate.


Can a transform lower the Kolmogorov entropy of a true random stream and then restore that stream with out loss

No. You can easily lower it, but can only restore add it in the form of a physical transform.


Not the answer you're looking for? Browse other questions tagged or ask your own question.