Randomness Course Notes

Definitions of Randomness

Kolmogorov

Complexity of a seqyence = The shortest algorithm that produces it

Martin-Löf

• A sequence is random is 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 shortest algorithm

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

My Idea

It might be possible to define algorithm in terms of a Turing machine. If the instructions of a Turing machine is 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 a 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 is needed to be encrypted with a secure key, the most secure way to produce a key is randomness.