Hacker News new | ask | show | jobs
by pcael 23 days ago
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.
1 comments

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).

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!
Not sure, I'm basing most of this on lecture notes I got at university.
thanks, dont they have a reference book? thanks
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