Connections in Math: the two kinds of random
stillthinking.net
Connections in Math: the two kinds of random
1–10 of 39 posts
Re: Connections in Math: the two kinds of random
#2I 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.
Re: Connections in Math: the two kinds of random
#3The thing that frustrates me about this argument is that there is no shortest program that produces pi. You need a computer to run it, which is massive non compressed data, or a human to calculate stuff, an uncountable amount of entropy.
I see that the irrational pi has a smooth distribution of digits and a file full of zeroes is compressible, but they are both sort of magically part of a world that does not run programs and thus not quite different in a practical sense.
Just my thoughts and sorry for the confusion.
Re: Connections in Math: the two kinds of random
#4I 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.
Re: Connections in Math: the two kinds of random
#5Lately 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 think what’s maybe more interesting is when you take into account the work of Dr. Futamura and the idea of Jones Optimality and view things through that lens.
Re: Connections in Math: the two kinds of random
#6The thing that frustrates me about this argument is that there is no shortest program that produces pi. You need a computer to run it, which is massive non compressed data, or a human to calculate stuff, an uncountable amount of entropy. I see that the irrational pi has a smooth distribution of digits and a file full of zeroes is compressible, but they are both sort of magically part of a world that does not run prog…
I think that does not hold, Kolmogorov complexity is measured relative to a pre-defined universal machine for everything. The machine is not counted in the description of π, for the same reason a book's length isn't measured by including the size of the reader. You fix one interpreter, then ask "how long is the shortest input that makes something?" The interpreter is a constant — the same constant for π, for the random file, for every string in the post
Re: Connections in Math: the two kinds of random
#7Lately 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…
Does that solve the issue? You can always ask yourself if you can embedd something smaller or not? Kolmogorov is just comparing things.. plus, in order to specifically point to pi in the languages internal table, you will need complexity as large as your representation of pi.
Re: Connections in Math: the two kinds of random
#8there are many instances of claude in here, so not sure what that disclaimer was about.
Re: Connections in Math: the two kinds of random
#9Lately 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…
His definition of Kolmogorov complexity is a bit loose. The rigorous definition uses Turing machines (or Minsky, or Post, or some sort of lambda expression, etc.) so the size is something specific. Different versions of complexity defined this way may give different values but have the same properties and asymptotics so one might just as well stick with the Turing kind. Chaitin's theorem (about the limit of Kolmogorov's complexity being just entropy) holds for all versions as well.
Re: Connections in Math: the two kinds of random
#10The choice of pi as a number whose sequence of digits is random is a bit of a weak point of the argument in the post. It is not even known whether every digit 0-9 appears infinitely many times in pi (a weak version of the normal number conjecture). So we do not really know (but strongly believe) that the sequence of pi digits would truly appear random. This of course does not detract from beautiful arguments and the general ideas in this post.