Randomness

⚡ Key Takeaways

Randomness is the absence of pattern, predictability, or deterministic cause in a sequence of outcomes. Key result: an outcome is random if it cannot be predicted with certainty and, over many trials, its outcomes follow a stable probability distribution. Where it applies: probability, statistics, cryptography, quantum physics, simulation, and games of chance. Who/when: formalized through probability theory (Pascal, Fermal, Kolmogorov) and algorithmic information theory (Kolmogorov, Chaitin, 1960s).

💡 The Core Insight

Randomness is individual unpredictability combined with collective regularity. A single fair die roll is impossible to predict, yet the long-run frequency of each face converges to exactly 1/6. This dual nature — chaos in the small, order in the large — is the engine behind all of probability and statistics. Randomness is not "nothing happening"; it is structure that lives only in the aggregate.

DefinitionSample Space and Probability

For a random experiment, the sample space $\Omega$ is the set of all possible outcomes. An event $A$ is a subset of $\Omega$ . A probability function $P$ assigns to each event a number satisfying the axioms below.

1

\quad 0 \le P(A) \le 1 \quad\text{for every event } A \subseteq \Omega

Derivation hint: a probability is a proportion of outcomes; proportions cannot be negative or exceed the whole, which equals 1.

2

\quad P(\Omega) = 1

Derivation hint: something in the sample space must occur, so the certain event has probability 1.

3

\quad P(A \cup B) = P(A) + P(B) \quad\text{if } A \cap B = \varnothing

Derivation hint: for mutually exclusive (disjoint) events, the proportions simply add since no outcome is double-counted. Symbols: $\Omega$ = sample space (all outcomes); $A, B$ = events (sets of outcomes); $P$ = probability measure; $\cup$ = union ("or"); $\cap$ = intersection ("and"); $\varnothing$ = empty set.

DefinitionEqually Likely Outcomes

When a finite sample space has $n$ outcomes that are all equally likely, the probability of an event $A$ containing $k$ favorable outcomes is:

4

\quad P(A) = \frac{k}{n} = \frac{\text{number of favorable outcomes}}{\text{total number of outcomes}}

Derivation hint: each of the $n$ outcomes has probability $1/n$ by symmetry; sum $1/n$ over the $k$ favorable outcomes by equation [3].

TheoremLaw of Large Numbers

Let $X_1, X_2, \dots, X_N$ be independent repetitions of a random experiment, each with mean $\mu$ . The sample average converges to the true mean as the number of trials grows:

5

\quad \overline{X}_N = \frac{1}{N}\sum_{i=1}^{N} X_i \;\longrightarrow\; \mu \quad\text{as } N \to \infty

Derivation hint: the variance of the average is $\sigma^2/N$ , which shrinks to 0 as $N$ grows; outcomes therefore cluster ever tighter around $\mu$ . This theorem is why randomness produces collective regularity: the relative frequency of an event approaches its probability.

DefinitionKolmogorov (Algorithmic) Randomness

A finite binary string $s$ is algorithmically random if its Kolmogorov complexity $K(s)$ — the length of the shortest computer program that outputs $s$ — is at least as long as $s$ itself:

6

\quad K(s) \ge |s| - c

Derivation hint: a compressible string has a short generating program (a "pattern"); a string with no shorter description than itself contains no exploitable pattern, the very meaning of randomness. Here $c$ is a small fixed constant. Symbols: $K(s)$ = Kolmogorov complexity of $s$ ; $|s|$ = length of $s$ in bits; $c$ = machine-dependent constant.

ProofThe Frequency Interpretation via the Law of Large Numbers

We show why the abstract number $P(A)$ matches the observed frequency of $A$ . 1. Indicator variable. For each trial $i$ , define $X_i = 1$ if event $A$ occurs and $X_i = 0$ otherwise. Then $X_i$ is a random variable. 2. Mean of the indicator. Its expected value is $\mu = E[X_i] = 1 \cdot P(A) + 0 \cdot (1 - P(A)) = P(A)$ . 3. Sample average is a frequency. The average $\overline{X}_N = \frac{1}{N}\sum X_i$ equals (number of times $A$ occurred) divided by $N$ — exactly the relative frequency of $A$ . 4. Apply the Law of Large Numbers (equation [5]): $\overline{X}_N \to \mu = P(A)$ as $N \to \infty$ . 5. Conclusion. The observed long-run frequency of an event converges to its probability. This is why probability, an abstract measure, can be measured by repeated experiments. $\blacksquare$

∎

AK

Andrey Kolmogorov

1903–1987

The Soviet mathematician Andrey Kolmogorov gave probability theory its rigorous modern foundation in his 1933 book Grundbegriffe der Wahrscheinlichkeitsrechnung, defining probability as a measure on a sample space — the framework in equations [1]–[3]. Three decades later he returned to randomness from a radically different angle, founding algorithmic information theory (equation [6]) by asking: what makes a single sequence random, with no reference to repetition? His answer — incompressibility — connected randomness to computation and complexity, unifying probability with the theory of algorithms.

🧠 Intuition

Picture two strings of 20 coin flips:

`HTHTHTHTHTHTHTHTHTHT`
`HHTHTTHTTHHHTHTTHTHH`

Both have probability exactly $(1/2)^{20}$ — they are equally likely outcomes! Yet the first "feels" non-random because we can describe it shortly ("HT repeated ten times"), while the second resists compression. This captures the deep idea: randomness is not about any single outcome being unlikely, but about the absence of describable pattern. Probability tells us how outcomes distribute; Kolmogorov complexity tells us which individual sequences deserve the name "random." A truly random sequence is its own shortest description — to communicate it, you must transmit every bit.

Figure

Individual unpredictability vs. collective regularity: as coin flips accumulate, the running fraction of heads wanders wildly at first, then locks onto 0.5.

ExampleRolling Two Dice

Given: Two fair six-sided dice are rolled. Find the probability that the sum equals 7.

Steps: 1. Total outcomes: each die has 6 faces, so $n = 6 \times 6 = 36$ equally likely ordered pairs (equation [4]). 2. Favorable outcomes summing to 7: $(1,6),(2,5),(3,4),(4,3),(5,2),(6,1)$ — that is $k = 6$ . 3. Apply equation [4]: $P(\text{sum}=7) = \dfrac{k}{n} = \dfrac{6}{36}$ .

\boxed{P(\text{sum}=7) = \frac{1}{6} \approx 0.167 \text{ (dimensionless probability)}}

ExampleEstimating π by Randomness (Monte Carlo)

Given: Random points are scattered uniformly in a $1 \times 1$ square; a quarter-circle of radius 1 sits inside it. Suppose $N = 10{,}000$ points are thrown and $M = 7{,}854$ land inside the quarter-circle. Estimate $\pi$ .

Steps: 1. The fraction inside should approximate the area ratio: $\dfrac{M}{N} \approx \dfrac{\text{quarter-circle area}}{\text{square area}} = \dfrac{\pi/4}{1} = \dfrac{\pi}{4}$ . 2. Solve for $\pi$ : $\pi \approx 4 \cdot \dfrac{M}{N} = 4 \cdot \dfrac{7854}{10000}$ . 3. Compute: $4 \times 0.7854 = 3.1416$ .

\boxed{\pi \approx 3.1416 \text{ (dimensionless)}}

This uses randomness constructively: the Law of Large Numbers (equation [5]) guarantees the estimate improves as $N \to \infty$ .

⚠️ The Gambler's Fallacy

A common error is believing that past random outcomes influence future independent ones — e.g., "the roulette wheel landed red five times, so black is now 'due'." For independent events, the probability resets every trial: $P(\text{black on next spin}) = 18/37$ regardless of history. Randomness has no memory. The Law of Large Numbers does not work by "correcting" imbalances; it works by diluting them as $N$ grows.

CounterexamplePatterns Do Not Disprove Randomness

One might claim a sequence like `HHHHHHHHHH` (ten heads) proves a coin is rigged. But for a fair coin this exact sequence has probability $(1/2)^{10} \approx 0.001$ — unlikely, yet equally unlikely as any other specific sequence such as `HTHTHHTHTT`. The appearance of a "pattern" in a finite sample is not evidence against randomness; truly random data inevitably contains apparent streaks and clusters. Conversely, forcing data to look "evenly mixed" (no long streaks) actually makes it non-random.

connection

Randomness is the foundation of Probability Theory, which quantifies it, and Statistics, which extracts signal from it. Its collective regularity is formalized by the Law of Large Numbers and refined by the Central Limit Theorem, explaining why the Normal Distribution appears everywhere. The algorithmic view (equation [6]) ties randomness to Information Theory and Kolmogorov Complexity, measuring it as incompressibility. In physics, Quantum Mechanics suggests randomness may be fundamental, not merely a reflection of our ignorance — a sharp contrast with the apparent randomness of Chaos Theory, where deterministic systems only look random due to sensitivity to initial conditions.

🔬 Where this appears

⏳ History

- ~3000 BCE: Ancient civilizations use astragali (knucklebones) for games of chance and divination — the earliest randomizing devices.

- 1654: Blaise Pascal and Pierre de Fermat exchange letters solving the "problem of points," founding mathematical probability.

- 1713: Jacob Bernoulli posthumously publishes Ars Conjectandi, proving the first Law of Large Numbers.

- 1733: Abraham de Moivre discovers the bell-shaped normal curve as a limit of coin-flip distributions.

- 1812: Pierre-Simon Laplace systematizes probability in Théorie analytique des probabilités, expressing a deterministic worldview (Laplace's demon).

- 1900: David Hilbert lists the axiomatization of probability among open problems (part of his 6th problem).

- 1933: Andrey Kolmogorov publishes the measure-theoretic axioms (equations [1]–[3]), giving probability rigorous foundations.

- 1940s: Stanislaw Ulam and John von Neumann develop the Monte Carlo method at Los Alamos for nuclear weapons calculations.

- 1960s: Kolmogorov, Ray Solomonoff, and Gregory Chaitin independently found algorithmic information theory, defining randomness as incompressibility (equation [6]).

open-problem

Deep questions remain about the very nature of randomness:

Is true randomness real? Quantum mechanics appears genuinely random, but "hidden variable" theories (constrained by Bell's theorem) keep the debate alive. Is the universe fundamentally indeterministic, or merely unpredictable to us?
Uncomputability of complexity: Kolmogorov complexity $K(s)$ (equation [6]) is provably uncomputable — no algorithm can calculate it in general. We therefore cannot certify, for any given finite string, that it is "truly random."
Pseudo-randomness: Computers generate only deterministic sequences that merely look random. Whether efficiently computable functions can be perfectly indistinguishable from randomness connects to the unsolved P vs NP question and the existence of cryptographic one-way functions.
Defining randomness for infinite sequences (Martin-Löf randomness, 1966) gives a robust notion, but multiple inequivalent definitions exist, and which one is "correct" remains a philosophical and mathematical frontier.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also