Definitions of Randomness

Kolmogorov

Complexity of a sequence = The shortest algorithm that produces it.

Martin-Löf

• A sequence is random if it passes all statistical tests.
• It cannot be produced by a program shorter than itself.

The digits of $\pi$ are not random in this sense.

Not just “difficult to compute”, there is no consistent way to define the shortest algorithm.

It’s impossible to find a way to ensure that a sequence is random. It’s similar to the halting problem in a way.

My Idea

It might be possible to define an algorithm in terms of a Turing machine. If the instructions of a Turing machine are shorter than the sequence itself, it’s not random.

Another idea

It says $P(b_n | s_{n-1}) = \frac{1}{2}$ for a binary sequence if the random process is ideal. But expecting this might be against randomness.

Pseudorandomness

Producing seemingly random sequences by algorithms, given a secret key.

The sequence is determined and can be inferred with high computing power. But for practical purposes, it’s random.

Uses of Randomness

• Randomized Algorithms: When a definite algorithm is too costly, it’s possible to run randomized algorithms for e.g. checking whether a number is prime.
• Cryptography: When a message needs to be encrypted with a secure key, the most secure way to produce a key is randomness.