Randomness Course Notes

2014-02-13

Definitions of Randomness

Kolmogorov

Complexity of a seqyence = The shortest algorithm that produces it

Martin-Löf

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