Kolmogorov Complexity | A Practical Introduction with Examples

Hi everyone, in this video I'll show you what Kolmogorov Complexity (or descriptive complexity or Kolmogorov–Chaitin complexity or algorithmic complexity or algorithmic entropy, or program-size complexity) is and how to estimate the upper bound practically. There is no code for this on my github because the code used here is super simple.

----

----
Follow Me Online Here:

___

Have a great week! 👋

[deeplearningexplained]

Here some references if you are interested:

1. MR178484 60.02 (65.15) Kolmogorov, A. N. On tables of random numbers. Sankhyā Ser. A 25 1963 369–376.

2. Chaitin, Gregory J. (1969). "On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers" (PDF). Journal of the ACM. 16 (3): 407–422. CiteSeerX 10.1.1.15.3821. doi:10.1145/321526.321530.

3. J. Ziv and A. Lempel, “A universal algorithm for sequential data compression, ” IEEE Transactions on Information Theory, vol. 23, no. 3, pp. 337–343, May1977.

[soumyakantiganguly]

Great Job !!! Another useful reference is the paper by by Per Martin Lof, "The Definition of Random Sequences". Information and Control 9, 602-619 (1966).

[roboticus]

Nice, thanks for explaining that for me.
One note, though: Your file_1 is twice the size of file_2, so the Kolmogorov complexity estimate is even more drastic. (File 1 is one million "ab", thus two million chars, file 2 is one million random chars.)

[JamesColeman]

Nice work, but why was the first file overall a larger file to start? Character quantity?

[quantummath]

Hi Yacine, I'm wondering what's the name of the background music? it's very nice.

[keremoguz]

Yeah but how do you calculate kolmogorov complexity??