Definition of randomness (sidebar: truth is random)

[phoenixthoth]

I find the definition of randomnumber at mathworld.wolfram.com rather unsatisfying.

Furthermore, dictionary.com will never help me decide what it means for an infinite sequence of numbers to be random.

I read this article once and I have changed it around a bit and I forget (nor can I find) the article. The rough idea is that a subset of N is random (ie it is a random list of numbers) if there is no (finite) formula corresponding to that set.

{1,1,1,1,...} is not random by this definition. f(n)=1 for all n specifies perfectly each term in this sequence.

Well, I think this might be a bit too model-theoretic for some but for the layperson there is some interesting conclusion involving Tarski's undefinability of truth theorem in arithmetic.

This is response to someone on IIDB named Alf about QM and randomness. Later, I challenge Alf to (1) well-define randomness and (2) prove that anything whatsoever in nature is random by this definition.

Also, I note that the set of tautologies corresponds fairly naturally (via Goedel numbering) to a RANDOM subset of N; thus one could intuitively though probably incorrectly decide that truth is random.

Here goes:
I however do not think rolling dice is random and therefore is at best a model for randomness. It's a rather poor example of something random, as is a pseudo-random number generator. In fact, I would go far as to say that we haven't yet both (1) well defined what randomness is and (2) been able to prove that randomness exists in nature.

It is safe to only consider defining randomness in terms of infinite sequences of numbers (which are functions from N to some set of numbers, N, Q, or R). An infinite sequence models the potentially infinite repetition of an experiment such as rolling a die. For example, {1,2,5,4,3,5,4,6,1,2,2,3,2,6,6,...} is a list of all the realized outcomes of rolling a die repeatedly. Thus I will define randomness for an arbitrary quantifiable event to mean that the sequence of numbers representing it is a list of random numbers where the definition of a set of random numbers follows.

I would define a sequence to be a random set of real (for example) numbers if that set is undefinable in (R,<,+,*). I tried to come up with sites that have a definition of definabliblity in model such as (R,<,+,*) and what I found are
http://plato.stanford.edu/entries/model-theory/ (keyword search for "definable") and
http://planetmath.org/encyclopedia/Definable2.html . Essentially, a set of real numbers is random if no formula specifies it. That formula could be said to "predict" what will be in that set and thus an aspect of the inherintly unpredictable nature of randomness is tied into this definition. Another, more intuitive definition of random sequence is that it is random if there is no finite formula for the function that it is (again, sequence is a function from N to R, for example). This entails that if a sequence is random and a formula gives to each N the right output in R then that formula is essentially just as big as N. Likewise, if there is a finite formula for the sequence then the sequence is not random. The sequence {1,1,1,1,1,1,1,1,1,...} is obviously not random: define f(n)=1 for all n. A finite formula.

(I think you'll find the gist of this quite interesting.) Do random sequences exist? Yes and I believe I have a nontrivial example that is quite interesting (even for the layperson). Take the set of all wffs (well formed formulas) in 1st order logic. Encode each formula by a number in the following way (essentially), called the Goedel number for the formula if you want to look it up: assign to each logical symbol si [s sub i] a number ai [a sub i]. Then take the formula and read what symbols appear in that formula and make a finite sequence of numbers (a1,...,an). Then use unique prime factorization, mapping this wff to a natural number, the encoding of the formula, by [formula]:=(p1^a1)*...*(pn^an). Here, given formula, [formula] is a notation for the Goedel number of that formula and pi is the i-th prime number (2,3,5,7,11,...). Thus we have a map from the set of all wffs to N. A unique number (by the uniqueness of prime factorization) comes from all formulas. Now consider the set of all tautologies, properly contained in the set of all wffs. Call this set of wffs T. T' is the set of all Goedel numbers of wffs in T. T is the set of all wffs that are in some sense true; i.e., T is the set of all truths. T' is the set of all of the encodings of all truths. Theorem T' is undefinable in (N,<,+,*). This is the so-called Tarski "undefinability of truth" theorem. The theorem says that if you have a finite formula F (which is redundant for wffs because all wffs are finite), then it is not the case that n e T' iff F(n) is true.

Now consider a sequence of all Goedel numbers of all tautologies. I don't care what order the tautologies are in though it is possible to list them all because the whole set of wffs is countable. Thus 316 might be the first number in this sequence where 316 is the Goedel number if some tautology (e.g., for all x, x=x). The second number might be 847826 which the Goedel number of some other tautology. So you have this sequence of Goedel numbers of all the tautologies. This sequence is random.

Thus one could pull a stunt and say truth is random. I wouldn't go that far because I've only made a statement about arithmetic. But "truth is random" is on some superficial intuitive level the conclusion; i.e., the set of all true statements is not definable; i.e., the set of all true statements is not predicatble by some finite formula.

There certainly are a bunch of tautologies so this is a genuine example of randomness.

I think I have well-defined randomness. What your burden is now is to prove that anything in nature corresponds to this or any well-defined notion of randomness.

Note that saying electon behavior is given by some probability distribution is not sufficient to prove randomness of said behavior. {(heads,.5),(tails,.5)} is a probability distribution but as we've seen, rolling a die is NOT random (it is chaotic).

 

[0rthodontist]

Well, the PlanetMath article involves some math that I don't know yet (stuck at the "models" symbol), but I can give a vague, philosophical answer that may be a misinterpretation. From a philosophical standpoint you can abstractly define anything--it depends on what you start with. If you start with R, <, +, *, then there are sequences that you can't define in a finite number of symbols. But if you start with T' instead of R, then it looks like you can define T' it in a finite number of symbols. If you start with T', <, +, *, can you define R in a finite number of symbols?

Edit: Well I have done a little more reading and maybe that last one is a dumb question, because R is not a subset of T'? But still, it looks like there is an easy algorithm to determine the elements of T' in order, namely go through each number and factor it and see if its factorization corresponds to a tautology through evaluating every possible assignment of truth values. So T' doesn't look random from that perspective.

The thing is that if you are just vaguely talking about a formula for the nth term of a sequence, it can be given. Even if you have some guaranteed random sequence, by whatever "random" means, there is probably some way of determining what the next item in the sequence is. If you start speaking your sequence out loud at a rate of one item per second, then I can define the n'th term of the sequence as the term you say in the n'th second.

 

[phoenixthoth]

Well, the PlanetMath article involves some math that I don't know yet (stuck at the "models" symbol), but I can give a vague, philosophical answer that may be a misinterpretation. From a philosophical standpoint you can abstractly define anything--it depends on what you start with. If you start with R, <, +, *, then there are sequences that you can't define in a finite number of symbols. But if you start with T' instead of R, then it looks like you can define T' it in a finite number of symbols. If you start with T', <, +, *, can you define R in a finite number of symbols?

Edit: Well I have done a little more reading and maybe that last one is a dumb question, because R is not a subset of T'? But still, it looks like there is an easy algorithm to determine the elements of T' in order, namely go through each number and factor it and see if its factorization corresponds to a tautology through evaluating every possible assignment of truth values. So T' doesn't look random from that perspective.

From mathworld.wolfram.com: "A theory is decidable iff there is an algorithm which can determine whether or not any sentence r is a member of the theory." Consider the incompleness theorem. I think it means that there actually is no effective algorithm or procedure for deciding if a formula about arithmetic is a tautology. I'm still unclear on this point. Maybe someone who knows more about this can throw us a bone?

The thing is that if you are just vaguely talking about a formula for the nth term of a sequence, it can be given. Even if you have some guaranteed random sequence, by whatever "random" means, there is probably some way of determining what the next item in the sequence is. If you start speaking your sequence out loud at a rate of one item per second, then I can define the n'th term of the sequence as the term you say in the n'th second.

But your formula would only necessarily fit the first n-1 numbers and not guaranteed to predict the n+1 number. Also, any finite sequence cannot be random which is essentially what I think you're saying.

 

[0rthodontist]

All right, I was confused about the term "first order logic," I was thinking of propositional logic. You are right, you can't just assign truth values to determine if a statement in first order logic is true.

But your T' still does not seem random to me. If it is impossible even in theory to decide whether some integers are elements of T', that doesn't strike me as randomness so much as some kind of ephemeral nonreality... No one can list the elements of T' in increasing order. They have to stop whenever they reach a number that corresponds to an undecidable statement.

Also, even if people can't list ALL the elements of T', they can still list many of them. If we have the same algorithm on our computers to try to decide whether x is an element of T', an algorithm which perhaps gives up after a while, then our results--which are guaranteed elements of T', though we may leave out some elements in between--are guaranteed to be the same. If you can recognize even SOME deterministic pattern in a sequence, and if you can tell what even only some of the as-yet-unseen elements of the sequence are, then it doesn't sound right calling it random.

 

[Hurkyl]

One of the funny things about probability is that random variables never actually take on values. So, if you insist on things taking values, then those things can't be random! (Of course, there are interpretations of QM in which observables don't actually take on values, in which case it would truly be accurate to say that they are "random")


There is a theorem of computability theory that says that "incompressible" and "random" strings "look the same". (The following is about finite strings)


We could talk about describing strings of digits. For example, we want to describe a string s of binary digits.

Suppose we have a program (specifically, a Turing machine) M, and some binary string w. Suppose that M(w) = s. (That is, if I run M on w, I get s as the answer) Then, we can use the pair <M, w> as a description of s. (For some reasonable way to encode a program and its input as a binary string)

We can define the descriptive complexity (or Kolmogorov complexity) K(s) of a string s by:

K(s) := min { |<M, w>| | <M, w> is a description of s }

Where |s| is simply the length of the string s.


A string s is said to be compressible if K(s) < |s|.


Note that K(s) depends on the method we use to encode a program and its input. Descriptive complexity is not well-defined for any individual input -- it only makes sense to speak about its bulk-properties.

For example, you can prove that at least half of the strings of a given size cannot be compressed. (for any particular scheme for describing strings)

But, for any individual string s, it is meaningless to ask whether s is compressible. (e.g. I can devise a scheme in which s is denoted by "0", and the binary representation of every other description <M, w> begins with a "1")


We can say if a property P holds for almost all strings: the fraction

|{s | |s| = n and not P(s) }| / |{s | |s| = n}|

goes to 0 as n goes to infinity.

If we have a computable property P (that is, one that can be computed by a program, aka Turing machine), then we have:

Theorem: Suppose P holds for almost all strings. Then P(s) is true for all compressible strings s, except for finitely many exceptions.

(This theorem actually has a slightly stronger statement, but I don't think it's necessary for this discussion)


In some sense, we would expect a property true for "almost all" strings to hold for almost all random strings. So, incompressible strings exhibit the same set of properties.


So, if you're willing to trade "randomness" for "incompressible", it is possible to speak about finite, random strings. But you are only allowed to speak about them in bulk, since the notion doesn't make sense for any particular string. (Or, I suppose, you could fix a particular representation of descriptive complexity, and speak relative to that)


(I've had this discussion in real life before. Can you tell? )


I'll have to think some more about infinite strings before I can decide what I want to say about them.

 

[phoenixthoth]

All right, I was confused about the term "first order logic," I was thinking of propositional logic. You are right, you can't just assign truth values to determine if a statement in first order logic is true.

But your T' still does not seem random to me. If it is impossible even in theory to decide whether some integers are elements of T', that doesn't strike me as randomness so much as some kind of ephemeral nonreality... No one can list the elements of T' in increasing order. They have to stop whenever they reach a number that corresponds to an undecidable statement.

Also, even if people can't list ALL the elements of T', they can still list many of them. If we have the same algorithm on our computers to try to decide whether x is an element of T', an algorithm which perhaps gives up after a while, then our results--which are guaranteed elements of T', though we may leave out some elements in between--are guaranteed to be the same. If you can recognize even SOME deterministic pattern in a sequence, and if you can tell what even only some of the as-yet-unseen elements of the sequence are, then it doesn't sound right calling it random.

That's a good point. I guess I just differ on that in so that I feel that if a sequence contains a nonrandom subsequence then it does not follow that the sequence is nonrandom.

 

[phoenixthoth]

That's basically more along the lines of the original article that inspired me to define randomness by the undefinable subsets.

 

[Hurkyl]

Yikes, that's a big quote!


Before I really say more, I'm pretty sure that ZFC has a definable model -- that is, the only sets that exist are those which uniquely satisfy some existential set-theroetic formula. (I may need to restate the axiom of choice to provide an actual logical mapping from sets to choice functions, though. I'm not sure)

If so, I think that there are no random subsets of N in this model.

I think you meant to say "sequence of natural numbers" and not "subset of the natural numbers" -- but my claim would hold for that too.



Your example of a "random" sequence fails, because it is the unique sequence s satisfying:

s is a sequence of natural numbers, and s(n) is the n-th smallest integer that is a Gödel number of a WFF that holds in every model of the natural numbers.


I think you need to use something weaker. For example, you could define:

A sequence s is said to be random if and only if it is not computable. That is, there does not exist a Turing machine M such that s(n) = M(n) for all indices n.

 

[0rthodontist]

I think that compressability is a good idea for randomness, but I think that the compression scheme is very important for determining if something is random, and it is random only in relation to a compression scheme. If some algorithm, or philosophically some person, can't reduce and summarize data very much, it means that the data is random _for that person alone_. Someone else might be able to compress the data very much, or even large sets of data, that the first person can't do anything with. No string and no set of strings (sufficiently small with respect to the length of the strings) by itself is random, it is only random with respect to the person or algorithm trying to analyze it.

 

[Hurkyl]

I suppose you could get by with just requiring the formula to be in a weaker language. E.G.

A sequence s of natural numbers is random if and only if there does not exist a unary relation P for which P(s) and E!x:P(x) are both in Th(N).

(I wonder if that is the same as the computable definition I gave?)


It strikes me that there are some quirky things that should be observed -- I don't know if you can elimiate them.

I strongly suspect that in any model of N, there exists a sequence s and a unary relation P in the language of arithmetic, such that P(s) is true in the model, E!x:P(x) is in Th(N), but P(s) is independent of Th(N).

It might even be possible that for any random sequence s, we can pick a model of N where the above can happen for s!

 

[0rthodontist]

On an intuitive level I just don't see how these definitions on the basis of noncomputability or satisfying/not satisfying formulas are connected with the idea of randomness. Undecidability is not randomness.

 

[Hurkyl]

Intuitively, randomness is unpredictability.

If a sequence is not computable, then there is no algorithm to predict its terms!

If a sequence is computable, then there is an algorithm to predict its terms.

So, intuitively, random sequences are precisely those that are not computable.


Alternatively, a random sequence is one that doesn't have any special properties.

Any formula that determines the terms of the random sequence would be considered a special property.

So, intuitively, random sequences are precisely those whose terms aren't determined by a formula.

 

[0rthodontist]

Randomness is unpredictability _of data_. If some terms of a sequence are noncomputable then _there is no data there_.

Anyway, and not to soften that point because I really think that's the heart of the issue, what about computation schemes that include oracles for undecidable problems?

 

[Hurkyl]

A sequence is computable if and only if there exists a (deterministic) program M such that M(n) is the n-th term of the sequence.

A noncomputable sequence just means that there does not exist a program that computes its terms. It doesn't mean that the sequence doesn't exist at all. :tongue:

An example of a noncomputable sequence comes from the Busy Beaver problem:

s(n) := the largest number that can be printed by a Turing machine with n states.


If you have an oracle, then you could talk about oracle-computable functions. The theory is all the same, you just have more computable functions. (And, of course, with a sufficiently powerful class of oracles, any sequence would be computable)

 

[0rthodontist]

Just because there's a term there doesn't mean there's data there. I'm basically winging this definition, but data has to be able to be input to something. If you can't figure out what the term is you can't input it to anything, nothing can plot it as a data point in any graph, it can't be used for any computational purpose. (well the abstraction of the term could but the abstraction of the term isn't the term). Data has to be real in a way that a computer can compute.

 

[Hurkyl]

Nobody said you can't figure it out -- just that there's no program that can do it.

For example, I could sit there and use my Geiger counter to figure out when my (infinitely large collection of) atoms decay, which gives me plenty of data to work with, but it might not be possible to write a computer program whose output is the same sequence of numbers.

 

[Hurkyl]

Or even just how long it takes a single atom to decay. I could use that to generate a sequence of integers (take the binary representation of the time it took to decay). It might not be possible for a computer program to spit out that sequence of numbers.

 

[phoenixthoth]

Before I really say more, I'm pretty sure that ZFC has a definable model -- that is, the only sets that exist are those which uniquely satisfy some existential set-theroetic formula. (I may need to restate the axiom of choice to provide an actual logical mapping from sets to choice functions, though. I'm not sure)

I think you need to use something weaker. For example, you could define:

A sequence s is said to be random if and only if it is not computable. That is, there does not exist a Turing machine M such that s(n) = M(n) for all indices n.

Very interesting. Thanks for the feedback.

I would like to study this model of set theory where x is a set iff f(x), where f is an existential 1st order formula. That certainly would mean that no subsets of N are lists of random numbers. Do you have more information on how this model is constructed for I thought that if we found any model for ZFC, then ZFC would be consistent and that it was not known whether ZFC is consistent. Am I wrong? Is this f built up in a constructive way or is it a pure existence of f theorem?

Your "weaker" definition of random is still capturing the idea that no function with finite formula perfectly predicts the sequence, right? What's the difference between my definition of a random sequence in the sense that are there random sequences in my definition that are not random in yours? Maybe T' is not a random subset of N. Could you eleborate on why in my definition T' is not a random subset of N?

So to more eloquently state my definition of random sequence, first it depends on what a random subset A of N is. A is a random subset of N iff by definition A is not definable in terms of the structure (N,<,+,*) [which may be redundant for I might be able to define < in terms of +]; i.e., there is no 1st order formula f such that n e A iff f(n). Then, a sequence NxS, where S is a set of numbers, is random iff S is a random subset of N. By this definition, since T' is a random subset of N, NxT' is a random sequence.

Your idea seems to be that there is no effective procedure for computing the sequence NxS. Which definition better encapsulates the unpredictability of randomness? If yours, then I'd readily adopt it.

Orthodontist, well, an infinite sequence is just a model of taking an experiment and repeating it forever. The sequence contains all of the data. I hope this is relevant to your question. "Thus I will define randomness for an arbitrary quantifiable event to mean that the sequence of numbers representing it is a list of random numbers where the definition of a set of random numbers follows."

 

[Hurkyl]

I would like to study this model of set theory where x is a set iff f(x), where f is an existential 1st order formula. That certainly would mean that no subsets of N are lists of random numbers. Do you have more information on how this model is constructed for I thought that if we found any model for ZFC, then ZFC would be consistent and that it was not known whether ZFC is consistent. Am I wrong? Is this f built up in a constructive way or is it a pure existence of f theorem?

I really ought to work through the details of this sometime. Maybe I'm fudging something I shouldn't.

If you allow me to adopt a suitable version of the axiom of choice (for simplicity, I will posit a well ordering < on the entire universe of sets)

For example, if Ax:P(x, y), then P(x, y) is clearly true for all definable x.

If Ex:P(x, y), then if y is definable, there is clearly a definable x satisfying the equation. Specifically, take x to be the smallest set (from the global well-ordering) satisfying P(x, y).

In other words,

Ex:P(x, y) ==> E!x: [ P(x, y) and (Az: P(z, y) => (x < z or x = z)) ]


I suspect the construction would be somewhat akin to constructing a term model for a set of sentences: I take my objects to be the formulas of the type E!x:P(x), modulo the relation that ZFC can prove the two sets equal.


I think would I have to assume the consistency of ZFC to construct this model -- maybe that will allay your concerns.


Alternatively, I assume (a first-order version of) ZFC to be consistent, from which I can conclude it has a model. I then select the substructure consisting only of objects that satisfy a formula of the form E!x:P(x), and then attempt to prove that this is actually a submodel of ZFC.

So to more eloquently state my definition of random sequence, first it depends on what a random subset A of N is. A is a random subset of N iff by definition A is not definable in terms of the structure (N,<,+,*)

Ah, I misunderstood -- I took "formula" to mean a formula of ZFC, not of the theory of interest. Your definition is almost the same as the one I gave.

As I said, I think there's an issue here with choice of model, which makes me unhappy.


I don't like your definition in terms of substs of N at all, though -- surely there can be random sequences that pass through each natural number at least once?


I really prefer defining things in terms of computability -- I think that's just a bias of mine, I don't necessarily know if it's better. And as I said, it's yet unclear to me just what the difference between the two methods would be.

 

[0rthodontist]

Or even just how long it takes a single atom to decay. I could use that to generate a sequence of integers (take the binary representation of the time it took to decay). It might not be possible for a computer program to spit out that sequence of numbers.

Does noncomputability really cover the case where there isn't any information to solve the problem? Is the question of whether there is a fully connected subset of size 5 in a graph that I will not specify to you, really noncomputable?

But note that the notion of compressability does fine for this. There is no program that can compress the set of integer sequences produced in that manner, unless there is a breakthrough in physics, which would lead to both a program that could do that and a good reason to consider those numbers nonrandom.

 

[matt grime]

Is the word 'computible' being used in its proper (turing machine) sense here at all? (I know Hurkyl was using it in this way.)

Given any graph there is an algorithm for 'computing if K_5' is contained as s subgraph. It just might take longer than the universe will exist for to work for any graph you actually give me. But that isn't what 'non-computible' usually means.

 

[0rthodontist]

No, I do not mean in a graph that the algorithm is provided with. I mean in a graph, as I said, that I will not specify. No algorithm could do that but does that mean that it is noncomputable? Just as, no (known) algorithm could predict the integers produced from measuring the decay time of an atom, but it has no data on which to start. It doesn't seem like either of those cases satisfies the formal meaning of noncomputable.

 

[Hurkyl]

Let me try restating the point.


We can have a Turing machine that spits out an infinite sequence of 0's and 1's.

There are countably many Turing machines.

There are uncountably many infinite sequences of 0's and 1's.

Therefore, there are uncountably many infinite sequences that absolutely positively, can never be seen as the output of a Turing machine. Those sequences are called noncomputable.


If I have an atom, and I measure the time it takes to decay, this allows me (in principle) to generate a sequence of 0's and 1's. It may be that this sequence is noncomputable.

In such a case, this means that it is impossible, even a posteriori, to devise a Turing machine that prints out the time it took to decay.

 

[0rthodontist]

Well, in practice you can only measure to a certain amount of precision, so your bit strings from atom decay will never really be "infinite" (and isn't the purpose of your example to illustrate an example of randomness by your definition under real conditions?)

Also, and more than likely I am misunderstanding or misinformed, is it true that every Turing machine either does not terminate or only outputs a finite length string? So you couldn't output the infinite string 1111... though that string is clearly not random.


When you look at this from the perspective of compressability rather than computability, it is all clear. The bit string from the atom decay is random because no one can compress (summarize) that data into a shorter form.

When you apply the compressability perspective to the tossing of dice, then you can say two things that satisfy both sides of the issue, that dice are somehow random yet also determined. If you are provided only with the output of the dice tossing, then that data is not compressible, so it is random. But if you are also provided with more information about the situation the dice were tossed in--velocity and rotation at which they left the hand, bouncing properties of the dice against the surface, as well as the actual outcome of tossing the dice--then you can compress that data because parts of it can be derived from other parts, so it is not fully random. So you can say that the physical system of tossing dice is nonrandom, while the outcome alone of tossing dice is random, which is satisfying from two perspectives at once.

 

[Hurkyl]

Well, there are (at least) two ways you can use a Turing machine to output an infinite string.

(1) Give the Turing machine a special output tape, to which it can do nothing but write a number and move the head to the right.

Then, the output of the Turing machine will be a (possibly infinite) sequence. That sequence is defined by saying the n-th term is the n-th symbol written to the output tape.

(2) Have a Turing machine that takes a number as input and returns a symbol as output.

This defines a sequence by saying that the n-th term is the result of running the Turing machine on input <n>.

When you look at this from the perspective of compressability rather than computability, it is all clear. The bit string from the atom decay is random because no one can compress (summarize) that data into a shorter form.

How are you going to define "compressability" for infinite strings?

The best definition I could imagine is:

An infinite string is said to be compressible if and only if there exists a Turing machine that can print it. (And thus the compressed form is simply the description of said Turing machine)

And thus, the compressible infinite strings are precisely those that are computable.


Furthermore, I don't think your definition is adequate. Maybe it's impossible to summarize that data in shorter form if you live in a vacuum... but it might become possible if you're allowed to refer to the initial conditions. If so, then I don't think the data could qualify as being "random".

 

[0rthodontist]

I think that's a reasonable definition of compressability for infinite strings--meaning, "infinitely compressible," or compressible to a finite amount of information. It doesn't work in other cases. For example, let j be an infinite bit string that anyone would agree is totally random (like your bit string from atom decay). Let k be an infinite binary string formed by replacing each 0 in j with 000, and replacing each 1 in j by 111. No program of finite length can print k. But k does not seem as random as j--it seems only about one third as random.

Another definition I can think of is that an infinite string is compressible if every finite prefix above a certain minimum length is compressible. Even though the summary of an infinite string might also be infinite, you can read the first n digits of the summary and derive more than the first n digits of the infinite string. So one compression of the first 3 * n digits of k is the first n digits of j, and reading the first n digits of the summary allows you to extrapolate the first 3 * n digits of the original string k, so k is "compressible" and not fully random.

I think that a compression scheme of randomness needs to take into account three things when deciding the randomness of some given data:
1. The data itself
2. Any context for the data (as in the dice example, where the context is the starting velocities and physical properties of the dice). Data + context = the "real" data set that the machine will try to compress, and statements about randomness can be made about data + context considered together, not about data alone.
3. The machine itself. What one compression machine is able to compress is not necessarily compressible by another compression machine. For example, let's say we have two compression algorithms, one designed to run on images and the other designed to run on English text. Data for an image seems mostly random to the English text compressor, and data for English text seems mostly random to the image compressor. I don't think this can be turned into a question of "does there exist a machine that can compress this" because the answer for finite data is always yes, there is always a machine that can compress all the data into one bit as you have mentioned earlier. I also don't think it can be profitably turned into a question of the existence of a machine to distinguish between many different data sets of the same type, because of the question of how you define what that type is. It has to be relative to the machine. Making it relative to the type that the data sets are considered part of just exchanges one relativeness for another, and it seems more natural (to me) to talk about the machine.

Statements about randomness of data are then really statements about randomness of (data + context) for a particular machine.

Furthermore, I don't think your definition is adequate. Maybe it's impossible to summarize that data in shorter form if you live in a vacuum... but it might become possible if you're allowed to refer to the initial conditions. If so, then I don't think the data could qualify as being "random".

I'm not sure what data you are talking about--the dice? Anyway, I may have addressed this point depending on what you mean.

 

[Hurkyl]

Hrm, that suggests two ideas to me.

The first would be some sort of asymptotic descriptive complexity -- you would define the asymptotic descriptive complexity of an infinite string to be the sequence whose n-th term is the descriptive complexity of its n-long initial segment.

Then, if the original sequence had complexity ~ f(n)

Let k be an infinite binary string formed by replacing each 0 in j with 000, and replacing each 1 in j by 111.

this sequence ought to have asymptotic descriptive complexity ~ f(n)/3.

I suspect this is immune to the usual ambiguity of descriptive complexity for finite strings.

3. The machine itself. What one compression machine is able to compress is not necessarily compressible by another compression machine. For example, let's say we have two compression algorithms, one designed to run on images and the other designed to run on English text.

I don't think we have to worry about that one. For finite strings, we know the "best" compression scheme: you encode your string s as <M, w> where M is a turing machine, and M(w) = s. The decompressor is simply a universal turing machine that reads <M, w> and runs M on w.

Any other scheme (for which decompression is computable) can only ever be better by some fixed additive constant... but fixed additive constants are irrelevant for our purposes!

The idea of the proof is that running your decompressor M on the compressed data w is the same as running the universal turing machine on <M, w>.



The other idea is to define a pre-ordering on strings. We define s <= t if and only if there exists a turing machine M that can print the first n symbols of s given the first n symbols of t as input. (In other words, there is enough information in the first n symbols of t to compute the first n symbols of s) Note that the same machine has to work for all n. Alternatively, s <= t "means" that t is "more random" than s. I wonder if this pre-order has any maximal elements? I wonder under what conditions two strings can compare equal!

 

[0rthodontist]

Hrm, that suggests two ideas to me.

The first would be some sort of asymptotic descriptive complexity -- you would define the asymptotic descriptive complexity of an infinite string to be the sequence whose n-th term is the descriptive complexity of its n-long initial segment.

Then, if the original sequence had complexity ~ f(n)

this sequence ought to have asymptotic descriptive complexity ~ f(n)/3.

I suspect this is immune to the usual ambiguity of descriptive complexity for finite strings.

I don't know about descriptive complexity. I was thinking more about compression, the ratio of the compressed form of the string to the length of the string, generalized to the asymptotic case. For j that ratio would be 1, for k that ratio would be 1/3.

I don't think we have to worry about that one. For finite strings, we know the "best" compression scheme: you encode your string s as <M, w> where M is a turing machine, and M(w) = s. The decompressor is simply a universal turing machine that reads <M, w> and runs M on w.

Any other scheme (for which decompression is computable) can only ever be better by some fixed additive constant... but fixed additive constants are irrelevant for our purposes!

For infinite strings a fixed constant (I assume you mean the length of M) is irrelevant, but I am also concerned with finite strings where a difference of 1000 bits for your encoder could mean the difference between compression and no compression (or "anti compression"). So for that reason it makes more sense to me to take M as a premise and then say the encoding is w. Because the length of M really should not matter for the randomness of the string. Besides, might not an unconventional program have infinite size?

The idea of the proof is that running your decompressor M on the compressed data w is the same as running the universal turing machine on <M, w>.



The other idea is to define a pre-ordering on strings. We define s <= t if and only if there exists a turing machine M that can print the first n symbols of s given the first n symbols of t as input. (In other words, there is enough information in the first n symbols of t to compute the first n symbols of s) Note that the same machine has to work for all n. Alternatively, s <= t "means" that t is "more random" than s. I wonder if this pre-order has any maximal elements? I wonder under what conditions two strings can compare equal!

I don't think that is the best ordering because let s be a string like j (totally random) and let t be s except that every block of 2 bits is reversed. So if s started (spaces used only for clarity)
01 01 01 01 11 01 00 10 01 then t would start
10 10 10 10 11 10 00 01 10

I think these strings should be considered to have equal randomness. But given any odd number of bits n in s, you can only compute the first n - 1 bits in t, and vice versa. I think a better definition is that s <= t iff the first n bits of t allow you to compute the first n - k bits of s, where k is some fixed constant and n is sufficiently large.

Though also, here's one to ponder. Let s be as before and let t be the string produced by first reversing the first two bits of s, then reversing the next 6 bits of s and appending them to the first two, then reversing the next 18 bits of s and appending them to the first 8, and so on, always multiplying by 3 the number of bits to reverse. Then it is not true that s<=t or t<=s even by my definition, yet they both seem equally random. And let u be the string produced by replacing every 0 in t by 00, and every 1 in t by 11. Then it is not true that s<=u or u<=s even by my definition, though obviously u is less random than s. So maybe we need another definition of <=.

You could say that t <= s iff comp(t) <= comp(s) where comp is the compression ratio. That is, let w(t, n) be the shortest encoding of the first n bits of t on a universal Turing machine. If lim(n->inf) (w(t, n)/n) exists and equals k, then comp(t) = k.

I guess I agree that for infinite strings it's better to ignore the machine and consider it part of the encoding so long as the machine is finite, or in other words to consider randomness only with respect to a universal machine.

Intuitively j would be a maximal element but maybe it is not possible for a string like j to exist in mathematics. In fact it seems like perhaps all infinite strings that can be defined are infinitely compressible. Letting j have noncomputable bits does not strike me as a reasonable approach. Noncomputable bits should be excluded from strings under consideration.


Anyway I am really more concerned with finite strings, since all data in the real world is finite.


But for infinite strings, here is how I imagine an infinite random string. A box is discovered with two lights on it, red and green. All attempts to break into the box fail; it is impervious to everything. The lights alternately flash, but no pattern can be detected in which light flashes at a given time. Every computer designed to compress any finite substring of the flashing lights pattern finds that for every substring other than the one it was designed for, its compression is on average nil. The nth light in the flashing lights sequence can be determined either by consulting the records or waiting for flash #n, but no computer without access to either the future or the past that contains that particular flash does better than chance at predicting what it is. And the same goes for any substring of the flashing lights sequence--every finite substring either is already known or can be known by waiting a while, but without access to that substring nothing can do better than chance at predicting what it is.

This box does not seem compatible with noncomputable bits, because each future bit _can be known_ just by waiting long enough, it just _can't be computed_ before then. Randomness must be knowable, but not computable.

 

[Hurkyl]

I've found a lead on the universe of definable sets:

http://en.wikipedia.org/wiki/Gödel_constructible_universe

I think this is exactly what I was talking about earlier.

 

[0rthodontist]

Well, that looks relevant but unfortunately I'm still clueless with that type of math. Maybe once I finish my course on language theory this semester I'll be able to discuss that more intelligently.


Here's a definition that I think captures your earlier idea of relative randomness, without having to compare compression ratios. (by the way I was extensively editing my post last night so I may have added stuff after you last read it--the last edit was 10:00 PM US Eastern time)

Given two infinite strings s and t, s <= t iff there exists some infinite sequence K = {n1, n2, ... } of natural numbers and a constant C, such if n $$\in$$ K then given the prefix of t of length n, it is possible to compute n - C elements of s along with their positions in s, though these elements need not be consecutive.

By this definition, I can't think of any examples where two strings s, t are derived from each other with apparent "equal randomness" without having s <= t and t <= s.

 

[Hurkyl]

Given two infinite strings s and t, s <= t iff there exists some infinite sequence K = {n1, n2, ... } of natural numbers and a constant C, such if n in K then given the prefix of t of length n, it is possible to compute n - C elements of s along with their positions in s, though these elements need not be consecutive.

There's a problem with this one, though.

Let s = {0, 0, 0, 0, ...} and t = {0, r1, 0, r2, 0, r3, ... } where the ri are a "random" sequence.

s and t would compare equal according to this definition, since I can always compute n bit & position pairs of one string given the first n of the other.

 

[phoenixthoth]

What brought this on was another thread on another board. I'm looking for a definition of random I can actually apply to individual sequences. He's arguing that the actual definition of random is "unpredictable" or "uncaused" and that the two are equivalent. I pointed out that you can have unpredictable with cause, so they're not equivalent. Uncaused, I went on to say, is hard (for me at least) to define mathematically so I will stick to "unpredictable." Predictable to me means compressibility in your Kolmogorov sense. What I'm ultimately trying to figure out is whether quantum events are truly random, and maybe uncaused. To get anywhere I have to have a definition of random. I'm trying to decide if "God plays dice." Of course one wonders where the "dice" (i.e., quarks and leptons and such) came from...

 

[Hurkyl]

There's an entirely different approach you can take to quantum randomness -- take modern probability theory seriously. Stop trying to think of experiments having outcomes: they're merely random variables. The dice never actually took on a value, although we would have facts such as

P((I saw a 1) or (I saw a 2) or ... or (I saw a 6)) = 1

and

P(you saw a 3 | I saw a 3) = 1

This is related to the many worlds interpretation (MWI), but I get the impression that the two aren't synonymous.

 

[0rthodontist]

Given two infinite strings s and t, s <= t iff there exists some infinite sequence K = {n1, n2, ... } of natural numbers and a constant C, such if n $$\in$$ K then given the prefix of t of length n, it is possible to compute n - C elements of s along with their positions in s, though these elements need not be consecutive.

There's a problem with this one, though.

Let s = {0, 0, 0, 0, ...} and t = {0, r1, 0, r2, 0, r3, ... } where the ri are a "random" sequence.

s and t would compare equal according to this definition, since I can always compute n bit & position pairs of one string given the first n of the other.

You're right... it can be patched by declaring the additional condition that for a given m, it is possible to choose an n large enough from K so that you can compute the first m digits of s given the first n digits of k. But I have no good reason for making that change.

The situation I made that definition to try to deal with was this: let s = {r1, r2, r3, ...} and let u be defined by {r1, r2, r4, r8, r16, ...}. Let v = the sequence of bits in s other than those in u. Now define t by the following:
i is even => ti = u(i/2) (edit from ui)
i is odd => ti = v((i+1)/2) (edit from vi)

t and s, it seems to me, should compare equal. But how to define it so it works that way?


Here is a definition of a totally random string. s is a totally random string iff for any n there exists a Turing machine M with an infinite output tape that can compute the first n bits of s on input 0, but for any such machine M there exists a number m (and m > n) such that the m'th letter on the output tape of M on input 0 does not agree with the m'th letter in s.

 

[Hurkyl]

Maybe they shouldn't compare equal! You've rearranged the terms, and maybe that rearrangement conveys some information? (or destroys some?)

Maybe it's similar to the problem of the information in concatenated strings: for example, for any scheme K and integer c, there exists (finite) strings x and y such that K(xy) > K(x) + K(y) + c.

Maybe we should try postulating the properties we would like our notion of complexity to have, and then trying to work out if there's any way to attain it!