24
$\begingroup$

What is a rigorous mathematical/logical definition of 'randomness'? Under what conditions can we truthfully apply the predicate 'is random'?

$\endgroup$
6
  • 5
    $\begingroup$ God does not play dice! $\endgroup$
    – user237393
    May 5, 2015 at 6:45
  • 2
    $\begingroup$ What about Satan? :D $\endgroup$
    – duskn
    May 5, 2015 at 6:50
  • $\begingroup$ cs.auckland.ac.nz/~chaitin/sciamer.html. It can be helpful $\endgroup$ May 5, 2015 at 6:59
  • $\begingroup$ There is a very nice discussion in Seminumerical Algorithms, Volume 2 of Knuth's book, The Art Of Computer Programming. $\endgroup$ May 5, 2015 at 7:09
  • $\begingroup$ I say, both God and Satan are sensible beings (like us) and hate randomness $\endgroup$
    – Spectre
    Oct 4, 2020 at 2:59

5 Answers 5

6
$\begingroup$

To avoid philosophical debates (I assume you are looking for the mathematical concept) one deals with random variables (they can be though as numerical characteristics of your experiment) which are functions defined on a probability space $(\Omega,\mathcal{B}, \mathbb{P} )$ $$X: \Omega \to \mathbb{R}$$

In order that this construction makes sense, one requires that you can ask some 'natural' questions about the result of your numerical characteristic such as: Is $X$ bigger than some $a$? what is the probability of this event?

You would like to consider $\{\omega \in \Omega : X(\omega) > a\} $ or briefly $[X>a]$. As $\mathcal{F}$ is the set of events, you require that $[X>a] \in \mathcal{F}$ then the probability of the event is given by $\mathbb{P}[X>a] \in [0,1]$.

that is, we require it to be a number between $0$ and $1$.

Lastly one demands that $\mathbb{P}[X\in \mathbb{R}] = 1$

An interesting point is the law of large numbers (a theorem) that states that as you repeat the experiment (with $X_1, \ldots, X_n, \ldots$ as the random variables representing the reproduction of the experiment (as independent random variables)) the mean value you observe converges to the probability on the event in question (almost surely ).

$$\lim_{n\to \infty} \frac{\sum_{j=1}^n 1_{[X_j >a](\omega)}}{n} = \mathbb{P}[A>a]\quad \omega\; a.s.$$

This is a remarkable result you may find a better discussion on Durret's Book ( Probability: theory and examples). I started there.

Now, if there is randomness in the world or if this is nothing but a useful model is a deeper question that requires more than the formal construction we made above. you should check this quote of Einstein "God does not play with dice" and contrast it with James Clerk Maxwell: “The true logic of this world is in the calculus of probabilities.”

a fuller discussion can be found on http://www.feynmanlectures.caltech.edu/I_06.html

Good luck

$\endgroup$
2
  • $\begingroup$ I'm not sure about that formula for the LOLN. $\endgroup$
    – wlad
    Jun 15, 2015 at 10:17
  • 4
    $\begingroup$ It's an interesting answer, alas not an answer to the question. $\endgroup$ Oct 4, 2020 at 1:55
5
+500
$\begingroup$

I think a serious explanation of a rigorous mathematical definition of randomness needs a considerable technical machinery. Hoping for an answer from an expert, here is at least a first step, admittedly for the most part informal.

Fundamental aspects of randomness can be described and explained with AIT - algorithmic information theory which was created and developed in large parts by Gregory Chaitin.

From the preface of the first edition of Information and Randomness - An Algorithmic Perspective by C.S. Calude:

  • While the classical theory of information is based on Shannon's concept of entropy, AIT adopts as a primary concept the information-theoretic complexity or descriptional complexity of an individual object. ...

    The classical definition of randomness as considered in probability theory and used, for instance, in quantum mechanics allows one to speak of a process (such as a tossing coin, or measuring the diagonal polarization of a horizontally-polarized photon) as being random.

    It does not allow one to call a particular outcome (or string of outcomes, or sequence of outcomes) random, except in an intuitive, heuristic sense. The information-theoretic complexity of an object (independently introduced in the mid 1960s by R. J. Solomonoff, A. N. Kolmogorov and G. J. Chaitin) is a measure of the difficulty of specifying that object; it focuses the attention on the individual, allowing one to formalize the randomness intuition.

    An algorithmically random string is one not producible from a description significantly shorter than itself, when a universal computer is used as the decoding apparatus.

So, AIT allows formalizing randomness of individual objects, which is a remarkable shift from the classical probability approach.

In chapter 26 of Randomness and Complexity G. Chaitin tells us informally about AIT in a nutshell. He speaks about his very first definition of randomness (1962):

  • Definition of Randomness R1: A random finite binary string is one that cannot be compressed into a program smaller than itself, that is, that is not the unique output of a program without any input, a program whose size in bits is smaller than the size of bits of its output.

This definition enabled G. Chaitin to connect game theory, information theory and computability theory. He worked on it and developed three models of complexity theory:

  • Complexity Theory (A): Counting the number of states in a normal Turing machine with a fixed number of tape symbols. (Turing machine state-complexity)

  • Complexity Theory (B): The same as theory (A), but now there's a fixed upper bound on the size of transfers-jumps, branches-between states. You can only jump nearby. (bounded-transfer Turing machine state-complexity)

  • Complexity Theory (C): Counting the number of bits in a binary program, a bit string. The program starts with a self-delimiting prefix, indicating which computing machine to simulate, followed by the binary program for that machine. That's how we get what's called a universal machine.

In each case, G. Chaitin showed that most $n$-bit strings have complexity close to the maximum possible and he determined asymptotic formulas for the maximum possible complexity of an $n$-bit string. These maximum or near maximum complexity strings are defined to be random. To show that this is reasonable, he proved, for example, that these strings are normal in Borel's sense. This means that all possible blocks of bits of the same size occur in such strings approximately the same number of times, an equi-distribution theory.

In order to develop this theory it was necessary to refine the definition of Randomness R1:

  • Definition of Randomness R2: A random $n$-bit string is one that has maximum or near maximum complexity. In other words, an $n$-bit string is random if its complexity is approximately equal to the maximum complexity of any $n$-bit string.

Nearly a decade and some brake-throughs later, in 1974, G. Chaitin had developed the theory to a point where he was able to formulate and concentrate randomness in his celebrated constant, the halting probability $\Omega$ (Chaitin's constant). It is based on a mature theory around the following:

  • Complexity Theory (D): Counting the number of bits in a self-delimiting binary program, a bit string with the property that you can tell where it ends by reading it bit by bit without ever reading a blank endmarker. Now a program starts with a self-delimiting prefix as before, but the program to be simulated that follows the prefix must also be self-delimiting. So the idea is that the whole program must now have the same property the prefix already had in theory (C).

All that work culminated in the definition of the halting probability $\Omega$. He published this model in A theory of program size formally identical to information theory in 1975. There are three key ideas in this paper: self-delimiting programs, a new definition of relative complexity, and the idea of getting program-size results indirectly from probabilistic, measure-theoretic arguments involving the probability $P(x)$ that a program will calculate $x$. He calls this the algorithmic probability of $x$. Summing $P(x)$ over all possible outputs $x$ yields the halting probability $\Omega$: \begin{align*}\Omega=\sum_{x}P(x) \end{align*} Or, equivalently as sum over all positive integers $n$: \begin{align*} \Omega^{\prime}=\sum_{n}2^{-H(n)} \end{align*} where $H(n)$ is the size in bits of the smallest program for calculating the positive interger $n$.

A key theorem is \begin{align*} H(x)=-\log_2P(x)+\mathcal{O}(1) \end{align*} which enabled him to translate complexities into probabilities and vice versa. Here the complexity $H(x)$ of $x$ is the size in bits of the smallest program for calculating $x$, and the $\mathcal{O}(1)$ indicates that the difference between the two sides of the equation is bounded.

$\Omega$ - A famous mathematical Constant

In order to get a glimpse of the kind of randomness which is distilled in $\Omega$ we take a look into section 11 in the first chapter of Mathematical Constants by S.R. Finch, which is devoted to Chaitin's constant. A remarkable connection of exponential diophantine equations with $\Omega$ is addressed:

  • An exponential diophantine equation involves a polynomial $q(x_1,x_2,\ldots,x_n)$ with integer coefficients as before, with the added freedom that there may be certain positive integers $c$ and $1\leq i<j\leq n$ for which $x_j=c^{x_i}$, and there may be certain $1\leq i\leq j<k\leq n$ for which $x_k=x_{i}^{x_j}$. That is, exponents are allowed to be variables as well.

    Starting with the work of Jones and Matiyasevic, Chaitin found an exponential diophantine equation $Q(N,x_1,x_2,\ldots,x_n)=0$ with the following remarkable property. Let $E_N$ denote the set of positive integer solutions $x$ of $Q=0$ for each $N$. Define a real number $\Omega$ in terms of $0.\Omega_1\Omega_2\Omega_3\ldots$ as follows: \begin{align*} \Omega_N= \begin{cases} 1\qquad\qquad \text{if }E_N\text{ is infinite},\\ 0\qquad\qquad \text{if }E_N\text{ is finite}\\ \end{cases} \end{align*}

    Then $\Omega$ is not merely uncomputable, but it is random too! ... Chaitin explicitly wrote down his equation $Q=0$, which has $17\,000$ variables and requires $200$ pages for printing. The corresponding constant $\Omega$ is what we call Chaitin's constant. Other choices of the expression $Q$ are possible and thus other random $\Omega$ exist. ... So whereas Turing's fundamental result is that the halting problem is unsolvable, Chaitin's result is that the halting probability is random. It turns out that the first several bits of Chaitin's original $\Omega$ are known and all are ones thus far.

Note that in C.S. Caludes book random objects with increasing complexity are studied. It starts with random strings and continues with random sequences and random reals, culminating in the derivation of $\Omega$ and related objects.

I'd like to finish this little trip by citing D. Zeilberger found in section 23.4 in Randomness and Complexity:

  • Greg Chaitin and the Limits of Mathematics:

    Standing on the shoulders of Gödel, Turing (and Post, Church, Markov and others), Greg Chaitin gave the most succinct, elegant and witty expression to the limits of our mathematical knowledge. It is his immortal Chaitin's Constant, $\Omega$: \begin{align*} \Omega:=\sum_{p\ \text{halts}}2^{-|p|} \end{align*} where the sum ranges of all self-delimiting programs run on some Universal Turing Machine. As Greg puts it so eloquently, $\Omega$ is the epitome of mathematical randomness, and its digits are beautiful examples of random mathematical facts, true for no reason. It also has the charming property of being normal to all bases.

$\endgroup$
2
  • $\begingroup$ Interesting answer, thank you. I wasn't aware of these books by Steven Finch. Long ago (ca. 2000), he had a website about mathematical constants, hosted by MathSoft (at that time, the developers of MathCad). He probably made a book version of the site. Here is the page for Chaitin's Constant, thanks to the Internet Archive: web.archive.org/web/20040204194231/http://www.mathsoft.com/… $\endgroup$ Oct 9, 2020 at 5:26
  • $\begingroup$ @Jean-ClaudeArbaut: You're welcome! Many thanks for granting the bounty and providing this interesting link. You're right, this is at least one of the sources for his book. I've checked other constants and they can be found partly verbatim in the book, very nice. :-) $\endgroup$ Oct 9, 2020 at 8:23
2
$\begingroup$

The following excerpt is from the first page of the introduction of Probability-1 by Albert Shiryaev. He discusses what it means to say something is random.

enter image description here

At the end of Probability-2, the second volume, he has a section called "Development of Mathematical Theory of Probability: Historical Review" that discusses "randomness" among other things. I can post it here if desired, as long as that doesn't contravene any rules.

If this answer is not considered helpful, let me know, and I can delete it.

$\endgroup$
0
$\begingroup$

Philosophy is unavoidable in answering this question, even as it applies to mathematics. Randomness is that property of some things, among them things such as items, events, collections, and patterns, which lacks what Aristotle would call an efficient cause; i.e. there is no mechanism or algorithm which can account for the particular property being observed. Note that an object per se (including a mathematical object such as a number like $\pi$) might be caused, but some property of that object, if that property is truly random, cannot be attributed to a causal mechanism or algorithm.

In the real world, where causality is presumed, true randomness must perforce be an abstraction or ideal that can be approximated but never achieved. In an abstract world, such as mathematics, randomness can be presumed axiomatically, but not proved, because a proof would entail an algorithm that dispositively accounted for or determined that property thought to be randomness.

$\endgroup$
1
  • $\begingroup$ In the 'real' real world, there are processes that, for all we know, must be truly random; quantum decay, particularly, is the canonical example. There is strong evidence both mathematical and physical that this process is truly random and that there are no 'markers' that one can use to determine specifically when it will happen. $\endgroup$ Oct 4, 2020 at 3:31
0
$\begingroup$

A definition I can give for randomness is this :

It is a condition in an experiment (mostly mathematical) such that one can't determine what comes next.

An example where this holds is in the tossing of an unbiased coin in conditions that ensure its unbiasedness. In such a toss, you can't exactly determine what would come next.

From the above example, it is clear to us that an experiment with random outcomes have equally likely outcomes , when considering each outcome as separate (i.e. , in the case of the rolling of an unbiased die, if you consider each number as separate and not subjecting them to conditions like 'the number is greater than $x$' or anything of that sort, each number has an equal probability of appearance).

Also, randomness has a specialty - it has no cyclic pattern (Ah.. that's just obvious).

For better answers, refer @ConradoCosta's or @Novice's answer.

$\endgroup$
4
  • $\begingroup$ "an experiment with random outcomes have equally likely outcomes" suggests that tossing a slightly biased coin would not have random outcomes. Many would disagree given the uncertainty. $\endgroup$
    – Henry
    Oct 7, 2020 at 12:07
  • $\begingroup$ @Henry , I don't understand what you mean to say. Could you please explain it to me ? Thanks. $\endgroup$
    – Spectre
    Oct 7, 2020 at 12:11
  • $\begingroup$ Suppose you have a bag with three balls (two red, one blue) and you draw a ball (equally likely any of the three) and note its colour. Many people would say the colour is random (unpredictable, based on chance, etc.) even though the probability of it being red is $\frac23$ rather than $\frac12$ $\endgroup$
    – Henry
    Oct 7, 2020 at 12:19
  • $\begingroup$ Well, I thought only about the unbiased experiments when I wrote this answer. Thanks for the help, @Henry $\endgroup$
    – Spectre
    Oct 7, 2020 at 12:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .