there are many instances of claude in here, so not sure what that disclaimer was about.
the entire website looks created by Claude and yes the text is definitely AI-generated. Putting that disclaimer there is just pathethic imo.
Connections in Math: the two kinds of random
31–39 of 39 posts
Re: Connections in Math: the two kinds of random
#32I 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 th…
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.
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).
Re: Connections in Math: the two kinds of random
#33I don’t understand the claim that Kolmogorov lower bounds are uncomputable. Three digit strings are unlikely to run as a program so surely 3 is a lower bound on Kolmogorov of the first million digits of pi, no? To tighten bound, one would need to try out every 4-digit program, every 5-digit program, and so on. Either these produce the first million digits of pi or they don’t when the program is run, so each possibili…
I agree, producing a lower bound is possible. It's practically very hard to give a good lower bound though. Many programs do not terminate, so we don't know if they do produce the right output eventually. In practice the best that has been done on Turing machines is that we have now proved which 5-state machines halt and which don't. So proving any lower bounds larger than that is practically impossible.
Ok got it, thanks.
Re: Connections in Math: the two kinds of random
#34Earlier quoted context omitted.
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.
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 distribu…
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!
Re: Connections in Math: the two kinds of random
#35Earlier quoted context omitted.
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 distribu…
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.
Re: Connections in Math: the two kinds of random
#36Lately I’ve felt Kolmogorov complexity is an unfair measurement because it takes for granted your underlying programming language as treats it as zero cost. In theory you could create a custom language and embed the program as data and “compress” a large random sequence with a better Kolmogorov complexity for that specific language than Pi, simply by not exposing the ability in the language to even work with Pi. I th…
You always include the measurement of things needed to run the program too. It's a bit like how benchmarks of compression utilities should always include the size of the utility itself. Otherwise someone can just submit a program with a dictionary of 256 common benchmark files for compression and claim "it compresses them to a single byte" :)
Of course you can. Kolmogorov complexity never says anything about finding lower bounds for specific elements. The lower bound is a statament about one string. The upper bound is statement about infinite strings, so you need to prove for infinite strings. In that sense you cant compress all strings and pointing a specific one without representing the index to it with a complexity a least as large as the string itself it represents. Read the part of pointing and telling things apart.
Re: Connections in Math: the two kinds of random
#37Earlier quoted context omitted.
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
Re: Connections in Math: the two kinds of random
#38Earlier quoted context omitted.
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
Re: Connections in Math: the two kinds of random
#39Earlier quoted context omitted.
> This is under-taught in comp sci so I'll say it in all caps for visibility. THERE IS NO KNOWN GENERIC WAY TO MEASURE INFORMATION ENTROPY!!!! Both your comment and the OP seem to conflate a distribution with a sample from a distribution. A distribution over strings has entropy. A single string can have a Kolmogorov complex but does not have entropy in the Shannon sense per se. When you write a compression algorithm,…
>A distribution over strings has entropy. You have to limit yourself to each string being independent for that to be true which is a limitation that leads to the impossibility of calculating entropy generically.
If you want to get correct answers out of math, it helps to start with correct definitions.
A random variable is a random variable and is not the same thing as a stochastic process. You now seem to be talking about stochastic processes, which are a different thing.
A stochastic process can have an entropy rate:
https://en.wikipedia.org/wiki/Entropy_rate
If you want to calculate entropy "generically" without defining what kind of entropy you're talking about, I think you are not likely to succeed.