What randomness really is

Question

I'm a Computer Science student and am currently enrolled in System Simulation & Modelling course. It involves dealing with everyday systems around us and simulating them in different scenarios by generating random numbers in different distributional curves, like IID, Gaussian etc. for instance. I've been working on the boids project and a question just struck me that what exactly "random" really is? I mean, for instance, every random number that we generate, even in our programming languages like via the Math.random() method in Java, essentially is generated following an "algorithm".

How do we really know that a sequence of numbers that we produce is in fact, random and would it help us, to simulate a certain model as accurately as possible?

Answer 1

The short answer is that no one knows what real randomness is, or if such a thing exists. If you want to quantify or measure the randomness of a discrete object, you would typically turn to Kolmogorov complexity. Before Kolmogorov complexity, we had no way of quantifying randomness of say a sequence of numbers without considering the process that spawned it.

Here's an intuitive example that was really bugging people back in the day. Consider a sequence of coin tosses. The outcome of one toss is either heads ($H$) or tails ($T$). Say we do two experiments, where we toss a coin 10 times. The first experiment $E_1$ gives us $H,H,H,H,H,H,H,H,H,H$. The second experiment $E_2$ gives us $T,T,H,T,H,T,T,H,T,H$. After seeing the outcome, you might be tempted to claim there was something wrong with the coin in $E_1$, or at least for some weird reason what you got is not random. But if you assume both $H$ and $T$ are as probable (the coin is fair), the probability of obtaining either $E_1$ or $E_2$ is equal to $(1/2)^{10}$. In fact, obtaining any specific sequence is as probable as any! Still, $E_2$ feels random, and $E_1$ does not.

In general, since Kolmogorov complexity is not computable, one can't compute how random say a sequence of numbers is, no matter what kind of claimed "totally random" process spawned it.

Answer 2

In the case of Java (or similar languages), we know the algorithm used to create the random numbers. If it starts with a single seed, the numbers are not random at all, i.e. if we know $a_i$ in a sequence $a_0,\dots,a_n$, we know $a_{i+1}$, or stated as conditional probability: $$\forall k,l,i: P(a_{i+1}=k\mid a_i=l)\in\{0,1\}$$

Nevertheless those series may fulfill properties (see e.g. WP:Autocorrelation) that random numbers fulfill and these properties often suffice to accomplish tasks, where we'd like to use "real" (e.g. generated by some physical process) random numbers, but can't effort them.

Answer 3

It is impossible to know for sure whether a given sequence is random or not. You can, however, look at characteristics (or parameters) of a sequence and calculate the probability of such a sequence given the distribution of interest.

If you could generate an infinitely long sequence using your random generator, it should have the same parameters as the random distribution. For example, if you are using the standard Gaussian distribution $(\mu=0,\sigma=1)$, then your sequence should be approaching the mean of 0 and the standard deviation of $1$. So, one preliminary way to check your generator is to generate a really long sequence and check to see that it is approximating the desired random distribution.

You can add additional moments of the distribution (such as skewness) of interest for further validation. For IID numbers, you could also try to train a machine learning algorithm to predict upcoming elements of the sequence and then test for the null hypothesis that the history improves the performance. None of these methods, however, can prove that a sequence is truly random and, at best, can recognize when sequences are NOT random (to some degree of certainty).

Answer 4

The modern theory of computing answer is "a random source is a source that looks random to your favorite class of algorithms". This is a utilitarian perspective: if a source of randomness looks like true randomness to all algorithms you care about, then nothing else matters. You can analyze your algorithms as if they are given truly random coin tosses, and your analysis will give the correct answers.

To be a bit more precise, let's say that you care about all algorithms in a class $\mathcal{A}$. $\mathcal{A}$ could be

• all Turing machines that always halt
• all polynomial size circuit families
• all polynomial time Turing machines
• all logspace Turing machines

The class $\mathcal{A}$ will be the "distinguishers". Then, a sequence of random variables $(X_n)$ where $X_n$ takes values in $\{0, 1\}^n$ is $\epsilon$-pseudorandom against $\mathcal{A}$ if for all $A \in \mathcal{A}$, $$ \left|\Pr[A(X_n) = 1] - \Pr[A(U_n) = 1]\right| \leq \epsilon, $$ where $U_n$ is a random variable distributed uniformly in $\{0, 1\}^n$.

This idea is behind any modern formal notion of pseudorandomness.

Answer 5

Here's two more cents.

One way to think about randomized algorithms is to picture a box that takes some input, does mysterious things to that input, and produces some ("unpredictable") output.

But instead, it might be helpful to think of them as deterministic algorithms that take two inputs: the "true" input, and some "random" inputs that we get from functions like Math.Random().

Now when we analyze the algorithm, we can make statements like this: "If our random inputs are uniform and independent on $[0,1]$, then with high probability our algorithm runs in time $n \log n$" or "with high probability the answer is correct".

This is a true fact about our algorithm. Now, a second question is whether the random inputs really do match this sort of assumption. I like the Bayesian sort of view that says this: Suppose that, to the best of my knowledge and beliefs, the randomness of my input is uniform and independent on $[0,1]$. Then the fact we proved above tells me what to believe about the output of my algorithm (namely, that it is very likely to run in time $n \log n$ or to be correct or so on).

As Jonathan and frafl mention, there are ways to sort of check if a random source is behaving "randomly". But all they will do is influence what you believe about future information that comes from this random source. If you think that each bit is equally likely to be zero or one, regardless of the previous bits, then to the best of your knowledge and beliefs, that source is uniformly and independently random and therefore, to the best of your knowledge and beliefs, it will run fast or be correct or so on. That's my philosophical take, anyway.

Answer 6

We cannot generate truly random numbers. There are different methods for generation of pseudo-random numbers using a specified equation and a particular seed value. So the random sequence of numbers depends on the seed value. Once we know the seed value, we can predict the what the sequence is going to be. Apart from this there are other methods for generating random numbers. People are now using some methods to generate true random numbers like using the disk head movement time and other physical methods which can be incorporated in a computer Refer to : http://en.wikipedia.org/wiki/Random_number_generation#Generation_methods

Answer 7

by the given method like you said
Math.random() in Java
Randomize; Random(n); in Delphi

you can implement your own structure and logic to generate random numbers,
where such "algorithm" can perform by your given specifications for better random results.
and build upon that the logics.

Thanks.

Answer 8

other answers are good, heres some other angles on this very important/unintentionally deep question. computer scientists have been studying randomness for decades and are likely to continue to study it. it has many deep connections and foremost open questions remaining throughout the field. here are a few pointers.

• "true/real randomness" occurs with low-level physical processes & "noise" such as in zener diodes, quantum mechanics etc. which can be harnessed in hardware based RNGs

• other numbers generated in the computer realm is what is known as "pseudorandom" which is simulated and can never match "true randomness". these are so-called PRNGs

• there is an important sense of "cryptographic hardness of random number generators" that in a sense measures their "quality" or "security" see eg cryptographically secure PRNG. basically a "weak" generator does not have as much computational complexity as a "hard" generator and a "weak" one is easier to break.

• another somewhat related sense it comes up is "hardness of proofs". imagine a proof to prove that a RNG is linear time $O(n)$. that proof would seem to be simpler than one required to prove it is quadratic $O(n^2)$ and so on. this concept is still in the process of being formalized/researched but it actually impinges on deep questions like P$\stackrel{?}{=}$NP in a famous paper called Natural Proofs. roughly, the authors show a P$\neq$NP proof must have a certain "complexity" otherwise the same analysis technique could be used to break PRNGs, and moreover, somewhat surprisingly, most or maybe all complexity class separations/techniques known at that date (or possibly even afterwards, to date) do not have sufficient complexity.

• an important research topic in TCS is randomized and derandomized algorithms. the idea is, roughly, to study how much the algorithm is altered by replacing "true randomness" with a PRNG and there are various deep theorems on the subject. here is a highranked cstheory.se question that gives some flavor of research in this area: efficient and simple randomized algorithms where determinism is difficult

• another key related topic in TCS is information entropy— originally introduced in physics long ago— which studies a closely related concept of "information dis-order" and like some other important concepts in (T)CS seems be one of the key ideas that crosscuts the boundary between applied and theoretical analysis, even some of the formulas are the same.

• again attesting to the status of active research, there are other high-ranked questions on cstheory.se that relate to this question. here is one close, almost the same: is a truly random number generator Turing computable