[contravariant]

I think the explanation of entropy's blind spot is a bit off. It's not actually a problem for entropy if something is generated by a rule, you can calculate entropy for things like the continuous fractions for instance, with an easy rule to generate them for any particular number. Likewise for decimal expansions.

The real blind spot is that entropy is meaningless for a specific sequence, you can't really ask about the entropy of pi if you don't have a theory for how the numbers are generated. Sure if it is pick a uniformly random real number between 0 and 10 then both files have equivalent entropy, but sending pi is also vanishingly unlikely.

There's actually a more subtle way in which this is a blind spot, which takes a bit more machinery. You can define entropy for an ergodic system, which could be considered a kind of mathematical RNG. Now as it turns out this provides a way to generate something almost equivalent to a particular distribution except that this argument only holds for most starting points not all. A direct example would be how pi generates a perfectly fine random distribution of digits (we think) but something like 1/3 does not.

[pcael]

thats interesting, and maybe beyond my current knowledge, I will certainly look into it. About the entropy being a property of a distribution, thats totally correct and I need to fix the post. Thanks.

[contravariant]

I think looking into ergodic theory would help fill in the gap between completely random and completely rule based. In ergodic theory you have some kind of 'state' and a function way to 'advance' the state, if you partition the state space you also get a sequence of 'bytes' to send (simple example: take a number in [0,1] multiply by 10, send the first digit and continue with the remainder). The state needs a distribution, that needs to be preserved by advancing the state, but it's pretty close to running an algorithm otherwise.

You'll probably also want to look at uniquely ergodic systems. Those are interesting in the way that they behave 'random' for every input, one example is if you keep multiplying a number by anything other than a power of 10 and divide it by a power of 10 so it's between 0 and 1. Turns out you get the same distribution of results every time (eventually).

And while you can define an entropy rate without I think ergodic theory also helps inform why that is the correct generalisation. Your current article only considers the case where each digit is independently random (it's clear why, it's a lot simpler and all that information theory tends to talk about).

[pcael]

Thats really interesting.. Do you recommend any books on ergodic theory that are accessible? I have undergrad in math, but it was a while ago. Thanks!

[contravariant]

Not sure, I'm basing most of this on lecture notes I got at university.

[pcael]

thanks, dont they have a reference book? thanks

[contravariant]

There are a couple of references, most on some obscure detail. The ones that might be worth a try for an introduction are:

- Walters, P., An Introduction to Ergodic Theory, Graduate Texts in Mathematics, 79. Springer-Verlag, New York-Berlin, 1982

- Billingsley, P. – Ergodic Theory and Information, John Wiley and Sons, 1965.

You may need a refresher on measure theory, or just ignore that part I suppose