## 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.