- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Russell Standish <R.Standish.domain.name.hidden>

Date: Wed, 17 Oct 2001 08:53:54 +1000 (EST)

juergen.domain.name.hidden wrote:

*>
*

*>
*

*> Confusion about what's a measure?
*

*> What's a distribution?
*

*> Simple but important!
*

*> For bitstrings x:
*

*>
*

*> M measure:
*

*> M(empty string)=1
*

*> M(x) = M(x0)+M(x1) nonnegative for all finite x.
*

This sounds more like a probability distribution than a measure. In

the set of all descriptions, we only consider infinite length

bitstrings. Finite length bitstrings are not members. However, we can

identify finite length bitstrings with subsets of descriptions. The

empty string corresponds to the full set of all descriptions, so the

first line M(empty string)=1 implies that the measure is normalisable

(ie a probability distribution).

As I said before, non-normalisable measures are considered measures by

the mathematical community - and the uniform measure over the set of

all descriptions is well defined.

*>
*

*> P probability distribution:
*

*> Sum_x P(x) = 1; P(x) nonnegative
*

*>
*

*> ---
*

*>
*

*> M semimeasure - replace "=" by ">=":
*

*> M(x) >= M(x0)+M(x1)
*

*>
*

*> P semidistribution - replace:
*

*> Sum_x P(x) <= 1
*

*>
*

*> ---
*

*>
*

*> Examples:
*

*>
*

*> 1. Distribution: E.g., integers n: P(n) = 6/(Pi n^2)
*

*> 2. Semidistribution: m(x) = probability of guessing a halting program
*

*> for x (BTW, Hal, this was first published by Levin in 1974, not by
*

*> Chaitin in 1975)
*

*> 3. Measure: E.g., each x of size n gets weight 2^-n
*

*> 4. Semimeasure: E.g., mu^M(x) = probability of guessing a halting or
*

*> nonhalting monotone TM program whose output starts with x
*

*>
*

*> Check out: Measures and Probability Distributions
*

*> Section 4 of "Algorithmic TOEs"
*

*> http://www.idsia.ch/~juergen/toesv2/node15.html
*

*>
*

*>
*

*>
*

*> Juergen Schmidhuber
*

*>
*

*> http://www.idsia.ch/~juergen/
*

*> http://www.idsia.ch/~juergen/everything/html.html
*

*> http://www.idsia.ch/~juergen/toesv2/
*

*>
*

*>
*

----------------------------------------------------------------------------

Dr. Russell Standish Director

High Performance Computing Support Unit, Phone 9385 6967, 8308 3119 (mobile)

UNSW SYDNEY 2052 Fax 9385 6965, 0425 253119 (")

Australia R.Standish.domain.name.hidden

Room 2075, Red Centre http://parallel.hpc.unsw.edu.au/rks

International prefix +612, Interstate prefix 02

----------------------------------------------------------------------------

Received on Tue Oct 16 2001 - 16:12:22 PDT

Date: Wed, 17 Oct 2001 08:53:54 +1000 (EST)

juergen.domain.name.hidden wrote:

This sounds more like a probability distribution than a measure. In

the set of all descriptions, we only consider infinite length

bitstrings. Finite length bitstrings are not members. However, we can

identify finite length bitstrings with subsets of descriptions. The

empty string corresponds to the full set of all descriptions, so the

first line M(empty string)=1 implies that the measure is normalisable

(ie a probability distribution).

As I said before, non-normalisable measures are considered measures by

the mathematical community - and the uniform measure over the set of

all descriptions is well defined.

----------------------------------------------------------------------------

Dr. Russell Standish Director

High Performance Computing Support Unit, Phone 9385 6967, 8308 3119 (mobile)

UNSW SYDNEY 2052 Fax 9385 6965, 0425 253119 (")

Australia R.Standish.domain.name.hidden

Room 2075, Red Centre http://parallel.hpc.unsw.edu.au/rks

International prefix +612, Interstate prefix 02

----------------------------------------------------------------------------

Received on Tue Oct 16 2001 - 16:12:22 PDT

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*