This is a short popular-science piece about randomness. It touches on randomness in several areas, including classical probability and statistics, derandomization in theoretical computer science, pseudorandomness in cryptography, and randomness in quantum mechanics. It is intended for interested readers.
Derandomization is a branch of theoretical computer science. Put simply, many algorithms need random numbers, and derandomization is the effort to design deterministic algorithms that do not need them.
For a long time, I was not very interested in derandomization. The reason was simple: in reality, we do not seem to lack randomness. Although von Neumann once said that "anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin"[1], today we have cryptographically secure pseudorandom number generators, as well as random sources that are relatively easy to obtain[2] [3]. In theory, many complexity theorists also believe that P = BPP, meaning that randomness does not give efficient computation any essentially additional power. Derandomization therefore looks like a less important problem: if random numbers are not hard to obtain, why work so hard to get rid of them? Going one step further, although we think random numbers do not add extra power in principle, removing them does weaken the computational power available in practice. Why remove them?
Only recently, after reading Noam Nisan and Avi Wigderson's work on hardness vs. randomness[4], did I realize that my previous view was too simple. I am not an expert in derandomization. Since the work of Nisan-Wigderson, there have also been works such as Impagliazzo-Wigderson and Babai-Fortnow-Nisan-Wigderson, all discussing closely related ideas: for an algorithm A(x,r) that originally uses random numbers, one can construct a pseudorandom generator from a hard function f and use it for derandomization, as long as A cannot distinguish the random string r from the pseudorandom string f(x). The argument is by contradiction. If A can distinguish them, that is, if the outputs of A(x,r) and A(x,f(x)) are noticeably different, then f is not hard.
It is important to emphasize here that f is hard for the algorithm A, but not necessarily hard for some other algorithm A'[5]. In other words, A can be viewed as a subjective observer with insufficient power, while f exceeds its capabilities, and is therefore hard for it, and therefore random. This line of thought immediately led me to make connections with randomness in other fields, which is how this article came about.
There is a Zhihu question, "What is the essence of probability?", but the discussion of randomness there is mostly centered on the frequentist and Bayesian schools. Descriptions such as "insufficient capability," "difficulty," and "subjectivity" do appear, but not very often. I think those answers do not get to the key point. The point this article tries to convey can be summarized as follows: Randomness is Hardness. More precisely, an observer has limited power. When something is too hard for the observer to understand or predict, the observer has to use probability and statistics. What the observer calls randomness comes from this hardness.
Next, let us continue exploring this theme through randomness in classical probability, cryptography, and quantum physics.
The simplest example of randomness is tossing a coin. After a fair coin is tossed, it has a 50% probability of landing heads and a 50% probability of landing tails. We can represent this with 0 and 1, obtaining the simplest possible discrete random variable. But there is a natural question: is tossing a coin really random? Imagine that, at the instant the coin leaves the hand, we could use extremely precise instruments to measure its angle, velocity, momentum, air resistance, the distribution of all the mass points in the coin, and the tiny states of the tabletop or the floor. Suppose further that we had enough computational power to incorporate all these physical quantities into a calculation. In principle, it seems we could then predict whether the coin would ultimately land heads or tails[6]. If this could really be done, then for someone with such measurement and computational capabilities, tossing a coin would no longer be a random event. It would merely be a complex but deterministic physical process. Yet for ordinary people, tossing a coin is still random. We cannot obtain sufficiently precise information during the brief flight of the coin, nor can we carry out sufficiently complex computations. Therefore, we can only describe it using probability: heads and tails each account for half[7]. The randomness here does not come from some mysterious force, but from the difficulty of prediction. In other words, coin tossing is random because it is hard for us to predict. Randomness is not absolute; it is relative to the observer's knowledge, tools, and computational power. For an observer powerful enough, randomness may disappear. For an observer with limited capabilities, randomness exists.
In cryptography, the relationship between randomness and hardness is even more direct. A so-called pseudorandom number generator starts from a very short random seed and generates a longer string of bits[8]. Strictly speaking, that string of bits is certainly not "truly random," because the output is longer than the seed and must therefore differ from a truly uniform random string. But cryptography is not concerned with whether it is ontologically random. It asks another question: is there an efficient observer that, without knowing the seed, can distinguish it from a truly random bit string? If no efficient algorithm can distinguish pseudorandom output from true random output within a reasonable amount of time, then this generated string of bits behaves like random numbers for those algorithms. This is a very clear idea: randomness can be understood as the difficulty of distinguishing. Whether a string of bits is random does not depend only on the string itself; it also depends on how powerful the observer or algorithm facing it is. If the observer lacks the ability to discover its structure, it will appear random. If the observer can identify the generative rule behind it, its randomness is broken. Thus, in the cryptographic setting, randomness likewise comes from hardness.
Quantum theory tells us that the hardness underlying randomness has an even deeper physical level. In the classical world, the randomness of coin tossing largely comes from insufficient information and insufficient computational power. As long as measurement is precise enough and computation is powerful enough, the result seems predictable, which is also why the idea of mechanical determinism exists[9]. But in quantum theory, when we measure a qubit in a superposition state, such as the simplest (1/√2)(|0> + |1>), we usually can describe the result only probabilistically: half the time it is |0>, and half the time it is |1>. In Section 37-6, "The Behavior of Electrons," of Volume I of The Feynman Lectures on Physics, Feynman gives an intuitive explanation of this point: the reason we can observe an object is that something, such as light, interacts with it and then carries information back to our eyes. But when the object being observed is as small as the microscopic scale, this act of "observation" itself can no longer be ignored. Our attempt to obtain information, for example by using light to hit an electron, inevitably affects the state of the electron being observed. Heisenberg summarized this as the uncertainty principle. Quantum theory is very deep, so I will not say too much here. But from Feynman's viewpoint, one can see that quantum randomness comes from a physical difficulty: observation necessarily affects the object being observed.
Finally, returning to the derandomization problem from the beginning, the process of derandomizing algorithms is in fact a process of gaining a deeper and more essential understanding of their internal structure. In my shallow understanding, it also has important connections with problems such as circuit lower bounds. The status of derandomization in theoretical computer science is far more important than it appears at first glance.
This is a translated version of my chinese post on Zhihu https://zhuanlan.zhihu.com/p/2039722685433951995
May 19, 2026