# Randomness Course Notes¶

Date: | 12632 |
---|

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