Connections in Math: the two kinds of random

Connections in Math: the two kinds of random(stillthinking.net)

48 points by pcael 69 days ago | 38 comments

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!!!!

Seriously. There isn't. You might say 'but measure the number of 1's vs 0's' and i'll just reply with '101010101010 repeated'. So you up it and start saying ok maybe measure frequencies of pairwise bits then and i just reply by cycling 00,01,10,11 endlessly etc. Frequency counts and any other measure you can think of doesn't actually work.

The root definition will state it's just based on the properties of the prediction but... what model do you use for the prediction? This gets to the heart of the matter;

The measure of information entropy itself is actually equivalent to creating on omniscient oracle. It requires being able to ask the question "Oh great oracle, what's the shortest program that can reproduce X"? or equivalently "What's the probability of this data assuming i always have the most perfect model to predict it?". You then calculate entropy based on that oracles answer.

Kolmorogorov, AI and information entropy are all pointing to the same thing. The reason people get confused by the fact that the frequencies of base 10 digits is the same for digits of pi and a truly random sequence is just because the counts of base 10 digits isn't a measure of entropy at all. Measuring entropy literally requires an omniscient oracle.

amluto 69 days ago | |

> 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, you are often effectively building an algorithm to look at a single sample from an unknown distribution (the input data) and trying to invent a distribution that is both easy to describe and that produces the input data with respectably large probability. And then you output the description of the distribution and enough data to identify the sample in question, and the latter takes space that is roughly the entropy of the distribution you just made up.

> "What's the probability of this data assuming i always have the most perfect model to predict it?". You then calculate entropy based on that oracles answer.

Careful here. The most perfect model may be the one that outputs the data in question with probability one, and the entropy is exactly zero.

If you want information theory to give you meaningful answers, you need to ask it more carefully specified questions.

AnotherGoodName 69 days ago | | |

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

strogonoff 69 days ago | |

Measuring information entropy seems to have parallels with the incompleteness theorem and with the hard problem. As we approach the seams (so to speak) in our ability to model the system in its own terms, our otherwise precise maps become distorted, things get self-referential and paradoxical.

contravariant 69 days ago |

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

contravariant 69 days ago | | |

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

tristenharr 69 days ago |

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

zzless 69 days ago | |

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.

adgjlsfhk1 69 days ago | | |

it's not just that they have the same asymptomatic. once you do the radix conversion (e.g. base 10 has log(10)/log(2) times more symbols), any 2 definitions are only off from each other by a constant

AnotherGoodName 69 days ago | |

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" :)

pcael 68 days ago | | |

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.

pcael 69 days ago | |

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.

doctor_phil 69 days ago |

Overall an interesting blog post, but the author makes this claim several times:

> So you can never close the case on even one candidate, let alone all of them at once, which means the lower bound stays sealed.

Which is simply not true. The specifics depends on what language you use, but let's take Turing machines as an example. Many candidates are easily disproven: ones that halt immediately, ones that have no rule for writing a "1", ones that have no rule for halting and so on. It's impossible to write a program that can handle every possible candidate though.

And if your string is short enough, let's say the string you are investigating is "0011" then you CAN sit down and check all Turing machines of size 4 and lower. This is essentially what the https://bbchallenge.org/ project did.

For Turing machines we have determined if they halt or not for all machines up to 5 states. It is very computationally hard to push this limit further, but we don't know where the theoretical limit is. We have some large upper bound where a Turing machine computes something that we know is independent of ZFC (see Scott Aaronson for more details), but many suspect that the limit is way lower.

superposeur 69 days ago |

I 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 possibility is checkable in finite time, no? There must be something I’m missing here.

doctor_phil 69 days ago | |

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.

superposeur 69 days ago | | |

Ok got it, thanks.

pwdisswordfishq 69 days ago | |

How long is the program which enumerates all N-digit programs?

hyperhello 69 days ago |

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

pcael 69 days ago | |

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

grammarxcore 69 days ago | | |

Sure, but spigot is a library, not the interpreter. The author’s program is short because it hides that.

zzless 69 days ago |

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

hahahaa 69 days ago | |

I thought every pattern is encoded in Pi. If so then by contradiction you need infinitely many 1s for example. If number of ones is finite number N, let pattern be 1 repeated N+1 times. =><=

Edit my presumption is an open question ;) I misremembered.

smalltorch 69 days ago |

I've been down this rabbit hole.

I tried to make a codebook of everything. You can get surprisingly good compression by assigning words and phrases to numbers.

My particular attempt had phrases up to 12 words.

No grammar or anything...to test the program, when I had a random thought, I tested to see if I could encode that thought. I could and on average the thought/message was compressed by 2. There was very few times where I wasent able to encode the idea into the available building blocks or language model of the database.

https://i.postimg.cc/WpBcB4HK/IMG-20260510-103853.jpg

andytratt 69 days ago |

there are many instances of claude in here, so not sure what that disclaimer was about.

elendilm 69 days ago | |

True. There is no shame in AI writing or human writing. Content is what matters. It appears the author is trying to fake genuinity in a fundamentally wrong way and yet doesn't even deliver on it.

MoltenMan 69 days ago | |

Yep. I'm already not a huge fan of reading AI writing, and adding an obviously false disclaimer at the top is ridiculous.

skybrian 69 days ago | |

Maybe the author has been overly influenced by Claude's writing style?

prox 69 days ago | | |

I think this is what we are going to see more and more, so people get exposed to the writing style and start to (un)consciously copy it.

altmanaltman 69 days ago | |

the entire website looks created by Claude and yes the text is definitely AI-generated. Putting that disclaimer there is just pathethic imo.

peterashford 69 days ago | |

how do you know?

zerobees 69 days ago | | |

The author admits it in the discussion of one of their other submissions: https://news.ycombinator.com/item?id=48799568

Apparently, the disclaimer was "put as a joke". Must be an eclectic sense of humor.

Ono-Sendai 69 days ago |

Kolomogorov complexity as an objective measure of the information contained in a string just doesn't work. It depends entirely on the language used for the program, and for any string, in some language, the complexity is zero.

See https://forwardscattering.org/page/Kolmogorov%20complexity

And no, the invariance theorem doesn't save you.