What Is Randomness?

When we say that a coin toss a random process, what we mean is that any possible sequence of the two potential outcomes is possible. But if we don’t expressly forbid any particular sequence, can we in fact claim anything at all? The foundations of probability theory and its application have always been a complicated topic for philosophers, but now this question has a more practical aspect: What can we expect from a random() function? Well, algorithmic information theory and complexity theory provide some tools to discuss these philosophical questions (algorithmic randomness, pseudorandom generators, etc.). In this lecture, we’ll discuss (on a non-technical level) the implications of all these things and more.
About the speaker:
Alexander Shen currently works as a researcher at LIRMM (CNRS, University of Montpellier, France), where he focuses on algorithmic information theory and algorithmic randomness. Prior to this, Alexander studied mathematics at MSU under the mentorship of V.A. Uspensky, later contributing his expertise to the Institute for Information Transmission Problems of the Russian Academy of Sciences (IITP RAS). Beyond these achievements, he has also co-authored several significant publications, including algorithmic theory and educational textbooks for both undergraduate and high school students.
00:00 - Intro
00:05 - What is randomness?
00:12:46 - How can we refute a statistical hypothesis?
00:21:42 - Canned randomness
00:34:10 - Randomness of an individual object
00:46:40 - Compressors and decompressors
#randomness #randomprocess