Algorithmic Information Theory II - Randomness

Perhaps a good point of view of the role of this chapter is to consider Kolmogorov complexity as a way of thinking.

Element of Information Theory, Second Edition,

Thomas M. Cover and Joy A. Thomas

. The theory [Quantum Mechanics] says a lot, but does not really bring us any closer to the secret of the "old one."

I, at any rate, am convinced that He does not throw dice.

A. Einstein

As science developed from antiquity to the present, it was recurrently faced with the question of thether nature is subject to chance to any extent, or evolved deterministically.

For most of that time the need to include chance was avoided by abstraction: the subject of study was so delimited as to allow its description as a deterministically evolving system.

As the theory of probability developed in modern times even chance came within the fold of predicability,

and the degree of abstraction could be lowered.

Chapter 2 Determinism

Quantum Mechanics, An Empiricist View

Bas C. Van Frassssen

In short, our gentleman became so immersed in his reading that he spent whole nights from sundown to sunup

and his days from dawn to dusk in poring over his books, until,

finally, from so little sleeping and so much reading, his brain dried up and he went completely out of his mind..

Don Quixote

Miguel de Cervantes

___________________________________________________________________________________________________

Define Randomness:

The Standard Example: Sitting with a friend , you flip a coin 100 times and get a Head every time. You claim that something is wrong with the coin. Your friend asks you why you said that. You show a sequence of a mix of 100 Heads and Tails $\$ and say that this looks what I should have gotten.

"What is the probability of what you got?" , asks your friend. you say. "And the probability of getting what you showed me?" "" you say

"And what's the problem with the coin?" ,your friend asks..

The Definition of a Probability Measure Revisited.:

Suppose we are given a set $\QTR{Large}{S}$ and a Sigma Algebra, a Probability Measure on $\QTR{Large}{A}$ is a function such that

If is a countable (again could be finite) subset such that for then $\QTR{Large}{P(}$

In the context of Probability, we will call $\QTR{Large}{S}$ the Sample Space.

The Usual Example:

Let $\QTR{Large}{S}$ be a finite set and $\QTR{Large}{A}$ a Sigma Algebra on $\QTR{Large}{S}$ . For any let $\QTR{Large}{n(B)}$ be the number of members in $\QTR{Large}{B}$ , then for all is a Probability Measure on $\QTR{Large}{A}$ .

DEFINITION:

Given a set $\QTR{Large}{S}$ , a Sigma Algebra $\QTR{Large}{A}$ on $\QTR{Large}{S}$ , and a countable discrete set $\QTR{Large}{D}$ , a Discrete Random Variable is a function $\QTR{Large}{X}$ $\QTR{Large}{:}$ such that if $\QTR{Large}{x}$ is in the image of $\QTR{Large}{X}$ then is in $\QTR{Large}{A}$ .

If $\QTR{Large}{D}$ , is finite then we will call $\QTR{Large}{X}$ a Finite Random Variable.

We write for
In the setting of 1. , if $\QTR{Large}{X}$ is a Finite Random Variable then

__________________________________________________________________________________________

The Really Super Computer Revisited:

The programs we are now interested are those that realize 1 to 1 recursive functions of the form ,

That is, if we load into our computer, write $\QTR{Large}{n}$ in the appropriate place in memory, and start the program, after a while the program halts and we find in the appropriate place in memory.
The Program - This program accepts as input a Natural Number and returns if is one of our target programs and if it is not. Again everything is to be thought of as taking place in The Computer. We will write (We should to verify that still can't be written but that is not relevant this discussion about Kolmogorov Complexity )
The Program - This program accepts as input a Natural Number $\QTR{Large}{n}$ and returns the number , the internal representation, of the $\QTR{Large}{\ n\ }$ th Target Program. We write

The Really Super Computer is now in a position to compute the corresponding

Really Random Sequences:

A definition for this discussion: A ( not necessarily anything ) function $\QTR{Large}{\ g:}$ is called really random If for any 1-1 recursive

is not recursive.
A definition for this discussion: A ( not necessarily anything ) function $\QTR{Large}{\ g:}$ is called really probabilistic

if, letting If there is a number such that for any 1-1 recursive

The Questions:

Is really probabilistic really random? For $\QTR{Large}{p=0}$ or $\QTR{Large}{1}$ . For
Is a really random $\QTR{Large}{g:}$ really probabilistic?

The Roulette Wheel , the Cell Phone, and the Winner's App:

The App can:

Calculate the velocity and acceleration of the ball in real time.
Calculate the velocity acceleration of the wheel in real time.
Predict the number that the will contain the ball.

____________________________________________________________________________________

The Definition of Kolmogorov Complexity:

Setting:

Unless otherwise stated, below the term "string" is , a string of $\QTR{Large}{0}$ s and $\QTR{Large}{1}$ s.

Definition:

Given a Universal Turing Machine, $\QTR{Large}{U}$ , the Kolmogorov Complexity, of a string $\QTR{Large}{x}$ is defined to the the length of the shortest program $\QTR{Large}{p}$ that prints $\QTR{Large}{x}$ and halts.

The following definitions, for Universal Prefix Turing Machines will be particularly relevent to the next lecture :

Prefix Kolmogorov Complexity is defined as the shortest program $\QTR{Large}{p}$ , for which the Universal Prefix Turing Machine $\QTR{Large}{U}$ outputs

Conditional Prefix Kolmogorov Complexity: (given a prefix encoding of $\QTR{Large}{y}$ )

Joint Prefix Kolmogorov Complexity:

____________________________________________________________________________________

Three Theorems and a Definition:

Theorem - Upper bounds:

There exists a constant such that

For Prefix Universal Turing Machines (The Prefix Encoding prefix +a very short program)

Proof:

The data on the input tape is $\QTR{Large}{x}$ and the program is copy the data to the output tape and halt.

Theorem - Invariance:

Given Universal Turing Machines $\QTR{Large}{U\ }$ and $\QTR{Large}{V}$ there is a constant . , such that for any $\QTR{Large}{x}$ :

Proof:

Since $\QTR{Large}{U}$ is Universal let be its emulation on $\QTR{Large}{U}$ . The rest of the proof amounts to noting that any program that can be run on $\QTR{Large}{V}$ can be run on $\QTR{Large}{U\ }$ using the emulation.

Definition:

A real -valued function $\QTR{Large}{f}$ is defined to be upper semi-computable if there is a "rational valued" recursive function such that:

For rational valued, read a numerator recursive function and a denominator recursive function.

Theorem - Incomputability But Upper Semi-computability

is not computable (recursive). It can be approximated from above, it is upper semi-computable.

Proof:

Essentially the Halting Problem or There are only finitely many programs of a certain size to be looked, but you can never be sure if they halt with the desired output. Maybe they just run forever.

___________________________________________________________________________________

Real Numbers:

Any finite string of 1 s and 0 s is primitive recursively enumerable.
The digits in the decimal expansion of $\QTR{Large}{\pi }$ appear to be randomly distributed.

Definition:

Let $\QTR{Large}{x\in }$ be real number and let

be its binary representation.

define

Definition:

$\QTR{Large}{x\in }$ is said to be algorithmically random if for some

all

Theorem:

Randomly chosen real number are algorithmically random with probability one.