Randomness Course Notes

Definitions of Randomness


Complexity of a seqyence = The shortest algorithm that produces it


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.


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