Randomness and Kolmogorov Complexity

What does it mean for something to be "random"? We might have an intuitive idea for what randomness looks like, but can we be a bit more precise about our definition for what we would consider to be random? It turns out there are multiple definitions for what's random and what isn't, but a particularly interesting idea is that of Kolmogorov randomness. Here, we take a look at Kolmogorov randomness (defined in terms of Kolmogorov complexity) to understand what the intuition behind it is and to develop a sense for what it really means for a sequence of values to be random.

0:00 Randomness
1:18 Kolmogorov Complexity
3:52 Kolmogorov Randomness

***

[hereigoagain]

Subjective Bayesian statistician here. Bayes (& Price) (1973) asked how to predict the next 0/1 if the sequence was extended. That is, not how to encode n binary digits but the prediction of digit n+1 given digits 1 to n. Of course, the answer depends on your model for generating digits. Great videos. Keep up the good work.

[yc]

Randomness is such a fascinating topic.
Something that always boggles my mind is the relationship between randomness and information density. It seems intuitive that true randomness must hold no information. But at the same time something that holds maximum information will be maximally close to randomness. Consider a string of text. It will hold information, but because of the redundancy you can compress it. So long as it is not maximally complex you can continue to compress it. Once you no longer can, it will pass tests for randomness. But at the same time is maximally information dense. So seemingly minimal entropy (maximum information density) is indistinguishable from maximum entropy (pure randomness). Am i missing something?

[AlexanderQ]

I was thinking the whole time about compressibility, I'm glad you touched on that

[MuazSikiric]

Awesome content! Can't wait to see the next video!

[itsundisclosed]

Heard the voice and instantly recognised you from CS50. Best of luck to you in life.

[Rickety]

Fibbonacci making his way into science videos again ❤️

[shadecreeper]

I feel like now with the breakthroughs in AI technology, a GPT AI could be used to come up with the shortest representation of data to determine how random it is. That could be fit into a function that determines the Kolmogorov complexity of data.

[michaeljoefish]

I define randomness as differing results coming from the same action assuming both happened at the same time. If I dropped a ball, and it bounced forward, and if I were to replay that same moment in time and it were to happen again, that wouldn’t be random. But, if I replayed the same moment in time with the exact same setup as before and got a different result, that would be random.

[phantom-ur]

There are actually rules and tests for the evaluation of random number generation algorithms. They are applied to pseudo-random number algorithms (which all "random" number algorithms in computers are), and only those that succeed can be used in critical systems, because otherwise they are a security vulnerability for important algorithms which rely on them, such as encryption key generators. There are several, but all of them describe aspects of one central requirement. Given any previously generated random result or sequence of random results, it is impossible to guess the next random result or sequence of random results with a greater probability then that sequence's chance to appear randomly. Basically, if you have 000 and the possible outcomes are 0 and 1, there should be a 50% chance the next is 0 and the next is 1. A flawed pseudorandom number generator, such as one which only produces infinite 0s, is flawed because you can predict with greater than 50% accuracy the next is 0.

[embee]

Fun topic, thanks for bringing this up.
I wonder how different would it be if we are looking for a random decimal number. 10101010 may not look random in binary but 170 could look pretty random.

[Bolidoo]

Would Rayo’s number be kolmogorov random? It’s easy to describe so definetly not “patternless”. Yet it’s not computable so it probably is kolmogorov random.

[w.harrison]

But how is a pattern found in the sequence? The examples you gave rely on the brain's pattern recognition; is there no algorithmic way that always finds the pattern in a sequence if the pattern exists?

[phillipotey]

It took me like 5 minutes to come up with a "function" to compute Kolmogrov complexity... only works for binary numbers though. Thinking "length" is a misnomer here.

[dontaskme]

very nice video, I hope you'll make more :) I'm not a fan of the background music though

[AabhusanAryalOfficial]

Can C(x) ever be greater than x? Context: 4:24

[BradenBest]

True randomness does not exist in reality, because to be "truly" random, a system has to be unpredictable yet at the same time be uniformly distributed, something which has an element of predictability and contradicts the previous requirement. If you remove the requirement for uniformity, then the only things that are random are things that are poorly understood, so then it's subjective whether or not something is "random". For example, if you have a trick coin where both sides are heads, the outcome of any flip is totally random to someone who doesn't know it's a trick coin or has no short term memory. To someone who does not know how to calculate pi, the digits of pi are random. To someone who does, they're not very random because they can calculate the digits themselves and anticipate future outputs. To an average super mario 64 player, the RNG is very random, but to pannenkoek2012 it's not random at all. You can make the argument that quantum fluctuations and cosmic noise are random, but really, for how long?

[peezieforestem]

In the broadest possible sense, randomess is inability to predict. In other words, there may well be patterns to the data, but you can't predict which one it is.

[andrewrigy]

"Inability to predict the rest of the sequence"

[networkedperson]

background music isn't loud and annoying enough

[mekkler]

There is no such thing as 'random', only sequences that we can't predict.