# 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}) = (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.