B What's the meaning of "random" in Mathematics?

[Buzz Bloom]

I'm not that surprised with that... these "randomness" tests also pass pseudo-random numbers, even if they are fully deterministic... I'd suspect that these "randomness" tests are incomplete, and pass as random sequences that are deterministic.

Hi fbs:

A randomness test gives a value that estimates the degree of close approximation a particular pseudo-random number sequence (e.g., the digits in pi) has to true random numbers. It is not intended to be complete.

Regards,
Buzz

 

[Buzz Bloom]

Appreciate it. I was stuck with the matter that logic is completely deterministic.

Hi fbs:

A deterministic process is by definition non-random. It is possible to voice logical statements about randomness, but such statements are not processes for generating random values. What they might be are statements that describe requirements about a process which are necessary for the process to create random values. For example, it is logical to say with respect to QM that measurements of the spin of a sequence of non-entangled particles produces a sequence of random values each of which is either "up" or "down".

Regards,
Buzz

 

[WWGD]

I don't know if this is too basic, but a variable is random if its outcome cannot be predicted with certainty. At best we can describe the distribution of the outcomes.

 

[FactChecker]

I don't know if this is too basic, but a variable is random if its outcome cannot be predicted with certainty. At best we can describe the distribution of the outcomes.

That certainly has advantages. For one thing, it is simple and as usable as any other definition. For another thing, it allows one to discuss the aspect that lack of available information plays in the inability to predict. One can reasonably think of randomness and probabilities in terms of the ability to guess and predict, given the information available. So the question of whether a result is really physically random or not is no longer appropriate -- it becomes a question of whether enough information is known to make the prediction. The second question is easier to agree on.

 

[WWGD]

That certainly has advantages. For one thing, it is simple and as usable as any other definition. For another thing, it allows one to discuss the aspect that lack of available information plays in the inability to predict. One can reasonably think of randomness and probabilities in terms of the ability to guess and predict, given the information available. So the question of whether a result is really physically random or not is no longer appropriate -- it becomes a question of whether enough information is known to make the prediction. The second question is easier to agree on.

Well, true, I am doing a good amount of assuming/black boxing. We may need to conduct tests on whether the variable ( and not a single output) is random. But at least these are some guide posts/ goalposts, and, yes, pretty tricky: what information , if any, would be needed to do a better approximation or estimation of the output? We may also have trouble with (somewhat_- pathological cases like Cauchy variables with infinite variance.

I can, tho, think of genuinely random variables when, e.g., using a pendulum oscillating between ( more than 1) magnets and seeing where it settles.

 

[fbs7]

Wow, many exquisite insights!

Let me ask you mathematicians this question: a pseudo-random sequence will repeat, even if after an absurd amount of time. But the digits of π do not repeat.

We know that neither of them are truly random, given that number n-th can be exactly calculated, although both cases "seem" to be random up to some measure.

But, given the fact that the digits of π do not repeat, does that make that sequence a bit more "random-ny" than a pseudo-random generator, if there's such thing? I fear I'm butchering proper mathematic-inglish again!

 

[FactChecker]

Wow, many exquisite insights!

Let me ask you mathematicians this question: a pseudo-random sequence will repeat, even if after an absurd amount of time.

That is a property of some specific methods of generating pseudo-random numbers. It is not a consequence of "pseudo-random" alone. Evan very good methods may fail sophisticated statistical tests, but they are adequate for most uses.

 

[Buzz Bloom]

But, given the fact that the digits of π do not repeat, does that make that sequence a bit more "random-ny" than a pseudo-random generator, if there's such thing? I fear I'm butchering proper mathematic-inglish again!

Hi fbs:

I am guessing that your question is whether it is possible for a randomness test method to determine if one pseudo-random number generator is better than another. I am also guessing that the answer is yes, and I am pretty confident this second guess is correct.

You should keep in mind that pseudo-random number generators are used with a specific purpose. It is desired that the pseudo random number generator used will give a result adequately close to what would be obtained using a true random number generator, e.g., something based on QM. If you can know theoretically what statistical result to expect form a sequence of random numbers used for a specific purpose, e.g., Monte-Carlo calculations, then the results of performing several Monte-Carlo runs with different pseudo-random number generators can be compared to determine which is the best for that particular purpose.

Regards,
Buzz

 

[andrewkirk]

Wow, many exquisite insights!

Let me ask you mathematicians this question: a pseudo-random sequence will repeat, even if after an absurd amount of time. But the digits of π do not repeat.

We know that neither of them are truly random, given that number n-th can be exactly calculated, although both cases "seem" to be random up to some measure.

But, given the fact that the digits of π do not repeat, does that make that sequence a bit more "random-ny" than a pseudo-random generator, if there's such thing? I fear I'm butchering proper mathematic-inglish again!

A pseudo-random sequence of numbers is just a sequence that has no readily apparent pattern, but is generated by a finite algorithm that takes no external inputs after the generation of the first M values (M is a fixed positive integer). Since the digits of pi are generated by an algorithm and its calculation takes no external inputs, they are a pseudo-random sequence.

So far as I am aware, it is not the case that a pseudo-random sequence must eventually repeat. It is just that non-repeating sequences become too slow to compute, the longer they continue, so the ones used by computers tend to be repeating for efficiency reasons. One way that I think will make a sequence non-repeating is as follows:

First, a definition: we say that a sequence of numbers, which may be finite or infinite, is 'repeating with lag L' if, for any j that is an index of the sequence such that j+L is also an index, the j-th and the (j+L)th element are equal.

The algorithm will use a simple, repeating, pseudo-random generator as its base. It generates positive integers.

Say we have already generated the first n numbers. Then for every k from 2 to (n+1), let m(n,k) be the quotient from dividing (n+1) by k and let r(n,k) be the quotient on dividing k by 2. For each k, there will be zero or one numbers such that, if that number is chosen, the last r(n,k) . m(n,k) elements out of the first (n+1) sequence elements, is repeating with lag m(n,k). Such a number is a 'forbidden number', as it creates a temporary repeat for a significant tail of the sequence thus far. Let F(n) be the set of all forbidden numbers at the step for generating the (n+1)th number.

Then generate a new number h(n+1) from the simple generator. Now chose as the (n+1)th number the closest positive integer to h(n+1) that is not in F(n).

I believe such a sequence will never repeat. But it will become progressively slower, because the number of checks that need to be made for each number increases as the sequence progresses.

But the sequence is pseudo-random because it satisfies the definition.

 

[fbs7]

Hmm... true point! I'm a programmer, so I should have seen that too, appreciate you pointing out.

Another example of a generator that will (eventually, and very very very slowly) not repeat is this one, for say 8-bit integers (or whatever size integers we choose):

initialize a[i] = 0 for i in 1..N
repeat
    calculate randomness of a[]
    for i = 1..N, for j = 1 to 8:
         invert bit j of a[i]
         recalculate randomness of a[]
         if new sequence has lower randomness, revert the bit back
   until randomness of a[] > desired-target

that algorithm (a brute-force search, actually) will eventually generate a non-repeating, whatever-length sequence that will pass whatever randomness criteria we set... at a cost of taking ages to process... hmm... actually this is probably the slowest random number generator ever... I should get a prize or something for that

hmm... actually I'm a bad programmer.. I should check for the thing hitting a hole, where any one-bit changes does not increase randomness; if one checks for valleys and holes and backtracks, the thing gets even slower...

 

[FactChecker]

Another example of a generator that will (eventually, and very very very slowly) not repeat is this one, for say 8-bit integers (or whatever size integers we choose):

initialize a[i] = 0 for i in 1..N
repeat
    calculate randomness of a[]
    for i = 1..N, for j = 1 to 8:
         invert bit j of a[i]
         recalculate randomness of a[]
         if new sequence has lower randomness, revert the bit back
   until randomness of a[] > desired-target

that algorithm (a brute-force search, actually) will eventually generate a non-repeating, whatever-length sequence that will pass whatever randomness criteria we set... at a cost of taking ages to process... hmm... actually this is probably the slowest random number generator ever... I should get a prize or something for that

It is notoriously difficult to design an algorithm for a random number generator. Anything that one thinks will be random is very likely to display patterns that are clear to see when looked at the right way. Your program looks like an example of that. A classic book which contains a lot on the subject is Knuth, "Art of Computer Programming, Volume 2: Seminumerical Algorithms" .

 

[PAllen]

It is notoriously difficult to design an algorithm for a random number generator. Anything that one thinks will be random is very likely to display patterns that are clear to see when looked at the right way. Your program looks like an example of that. A classic book which contains a lot on the subject is Knuth, "Art of Computer Programming, Volume 2: Seminumerical Algorithms" .

As an example of the notorious difficulty, all of the touted best algorithms in the 1981 edition of this book are now considered inferior, obsolete algorithms as randomness testing improved, and uses became more sensitive to multidimensional correlations (which plagued the most touted algorithms of the 1981 edition). I do not know if there is a more updated edition; the 1981 is the only one I have.

However I still strongly recommend it as the only book I know of to develop a robust theory of pseudo-randomness in a sequence.

 

[FactChecker]

There are entire texts now on random number generators that, I assume, are more modern and comprehensive. Unfortunately, I am not up to date on any new developments.

 

[Auto-Didact]

I can, tho, think of genuinely random variables when, e.g., using a pendulum oscillating between ( more than 1) magnets and seeing where it settles.

This screams determinstic chaos to me i.e. completely non-random, but merely unpredictable for all practical purpose (FAPP) due to limited measurement precision, firstly because of practical reasons and secondly because of the uncertainty principle in QM.

Another popular example of deterministic chaos in which the pattern seems random is the Lorenz water wheel, where it quickly becomes impossible to predict which side the wheel will turn or how it began turning, yet its complete dynamics is fully described by an attractor in state space.

 

[FactChecker]

As an example of the notorious difficulty, all of the touted best algorithms in the 1981 edition of this book are now considered inferior, obsolete algorithms as randomness testing improved, and uses became more sensitive to multidimensional correlations (which plagued the most touted algorithms of the 1981 edition). I do not know if there is a more updated edition; the 1981 is the only one I have.

However I still strongly recommend it as the only book I know of to develop a robust theory of pseudo-randomness in a sequence.

The algorithms of that time would show high autocorrelations at particular high lag amounts. The use of Box-Jenkins time series analysis implemented on computers easily identified weaknesses that would otherwise not be noticed. Those algorithms were perfectly adequate for most uses in simulation, but not if very sophisticated statistical analysis of the results was to be done. I felt that the weaknesses were noticed in the academic world but usually did not matter in real-world applications.

 

[PAllen]

The algorithms of that time would show high autocorrelations at particular high lag amounts. The use of Box-Jenkins time series analysis implemented on computers easily identified weaknesses that would otherwise not be noticed. Those algorithms were perfectly adequate for most uses in simulation, but not if very sophisticated statistical analysis of the results was to be done. I felt that the weaknesses were noticed in the academic world but usually did not matter in real-world applications.

For most applications, yes. However a former physics professor of mine bumped hard into the fundamental limits of linear congruential gemerators doing Monte Carlo simulation in high dimensional phase space.

 

[jedishrfu]

Years ago when I was a newbie programmer, a senior programmer told me the story of one such pseudo random generator program.

It was a new and better algorithm that looked totally random according to initial tests.

However, it wasn't until the random sequence elements were grouped into triplets and plotted in 3D that it was discovered that they all fell on the same plane.

 

[StatGuy2000]

I'm surprised that no one on this forum mentioned that there are in fact different definitions of randomness depending on what context you are using.

For example, there is a notion of statistical randomness. A numeric sequence is said to be "statistically random" when it contains no recognizable patterns or regularities. Note that sequences that are statistically random doesn't necessarily imply "true" randomness in the sense of objective unpredictability, since a deterministic process (such as the calculation of the digits of π) can generate such a statistically random sequence (thus the utility of pseudorandom number generators).

There is another way in which randomness is defined in mathematics. The field of algorithmic information theory studies, among various topics, what constitutes a random sequence. The central idea is that a string of bits is random if and only if it is shorter than any computer program that can produce that string (called Kolmogorov randomness, after Russian mathematician Andrey Kolmogorov who had developed this definition, which were also independently developed by American computer scientist Ray Solomonoff and American mathematician Gregory Chaitin).

 

[fbs7]

Wow! That is awesome! Information theory at its finest!

If you cannot compress a string (by calculating it with a program) then the string is random. Mind-blowing! So "abababababababababababababab" is not random, and neither is "abcdefghijklmnopqrstuvwxyz". I'm starting to like this Kolmogorov guy a little more!

Or not... hmm... say I give this string "azi843ad8$@$%po#$cd2904". Then if I could write a tiny program that calculated it, then I know it's not random. But if I can't write that program, how could I prove it's a random string by proving that nobody ever anywhere in the history of the Universe could write a small program that by doing adds/multiplications/etc... would calculate that string. Not liking Kolmogorov any more... he seems to have the habit of frying other people's brains!

 

[FactChecker]

Wow! That is awesome! Information theory at its finest!

If you cannot compress a string (by calculating it with a program) then the string is random. Mind-blowing! So "abababababababababababababab" is not random, and neither is "abcdefghijklmnopqrstuvwxyz". I'm starting to like this Kolmogorov guy a little more!

Or not... hmm... say I give this string "azi843ad8$@$%po#$cd2904". Then if I could write a tiny program that calculated it, then I know it's not random. But if I can't write that program, how could I prove it's a random string by proving that nobody ever anywhere in the history of the Universe could write a small program that by doing adds/multiplications/etc... would calculate that string. Not liking Kolmogorov any more... he seems to have the habit of frying other people's brains!

It seems that the rule of the program must be larger than the result works well as a definition, but proving such a thing for a given sequence is hard.

 

[fbs7]

Also how to prove an infinite string is random through that rule? It seems to come down to computability... if that string can be calculated through a program, then (I suspect programs cannot be infinitely big) then it won't be random...

Hmm... lots of room for exoteric thought, I suspect... say a sequence is defined through a formula, but that formula cannot be exactly calculated through a program, but only approximately... say the irrational roots of a generic 5th-degree polynomial; I can't write a program that computes that root exactly, so would that mean that the digits of that root are random? Ay-ay-ay... I'm liking Kolmogorov less and less every day!

 

[SSequence]

Hmm... lots of room for exoteric thought, I suspect... say a sequence is defined through a formula, but that formula cannot be exactly calculated through a program, but only approximately... say the irrational roots of a generic 5th-degree polynomial; I can't write a program that computes that root exactly, so would that mean that the digits of that root are random?

I think 5-th degree polynomials would fall into category of algebraic numbers (at least if the coefficients are rational) and hence into domain of computable numbers (assuming the "decimal expansion" def. here). I suppose one could use any "approximation methods" of solution (that are in fact usually implemented on actual computers I think) that can calculate the decimal positions to arbitrary high accuracy.

 

[jbriggs444]

Also how to prove an infinite string is random through that rule? It seems to come down to computability... if that string can be calculated through a program, then (I suspect programs cannot be infinitely big) then it won't be random...

You would fix the program (for instance, use a particular Universal Turing Machine) and cast the problem in terms of how much input would be required to produce a given amount of output. Then take the limit of the ratio of the input size to the output size as output size increases without bound.

If the output string is chosen from a uniform distribution (i.e. all prefixes of a given length are equiprobable) then one has all of the tools in Shannon's bag to demonstrate that the input size must be, on average, at least as large as the output size.

If one has an infinite string produced from a loaded die then, with probability 1, the limiting ratio of input size to output size will reflect the Shannon information content of the string.

 

[StatGuy2000]

Also how to prove an infinite string is random through that rule? It seems to come down to computability... if that string can be calculated through a program, then (I suspect programs cannot be infinitely big) then it won't be random...

Hmm... lots of room for exoteric thought, I suspect... say a sequence is defined through a formula, but that formula cannot be exactly calculated through a program, but only approximately... say the irrational roots of a generic 5th-degree polynomial; I can't write a program that computes that root exactly, so would that mean that the digits of that root are random? Ay-ay-ay... I'm liking Kolmogorov less and less every day!

@jbriggs444 has suggested one way to prove an infinite string is random in post #74. Another way, courtesy of Swedish mathematician Per Martin-Lof, who had proposed the following defintion:

An infinite sequence is random if and only if it withstands all recursively enumerable null sets.

If you want more technical definition, please see the following Wikipedia article:

https://en.wikipedia.org/wiki/Algorithmically_random_sequence#Three_equivalent_definitions

 

[SSequence]

You would fix the program (for instance, use a particular Universal Turing Machine) and cast the problem in terms of how much input would be required to produce a given amount of output. Then take the limit of the ratio of the input size to the output size as output size increases without bound.

Yes I think a definition based on incompressibility (for a sequence) seems to be an interesting one. Though I am a bit fuzzy about translation of terms between numbers and strings (also because I haven't really studied computability based randomness) ... since almost always people seem to cast information complexity in terms of strings, but it seems that it could also be re-cast in terms of numbers (with small modifications).

Something else that seems interesting (unless I am missing something due to unfamiliarity with topic at hand) to is that, if we are talking about numbers, apparently an appropriate version of BB function will be compressible (rather in a pronounced way).P.S.
What is interesting is that what you wrote was essentially what I cast as question in the other thread (with the necessary modification, due to nature of construction, of replacing universal program with ordinal universal program). I should have seen the problem anyway (even without information complexity) because of the reason I mentioned in that thread (since application of such method to a very small ordinal like $\omega_{CK}$ should be a sure sign of a problem with a construction).

 

[Mark44]

Though I am a bit fuzzy about translation of terms between numbers and strings

The strings that are mentioned by most of the people responding are strings of bits -- 0s and 1s.

 

[SSequence]

Yes, I understand this. In the same way basically we could take any "positive number" to be a regular expression of form:
(1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)*
where the alphabet is obviously the set {0,1,2,3,4,5,6,7,8,9}.

What I meant was the usage of same terms (compressibility, kolmogorov complexity) using different computational models (normally ones that are assumed are ones manipulating strings) that involve "strings" OR "numbers". Since I haven't studied this topic, I was just saying I am unsure how these (presumably robust concepts) would translate between different languages (that use strings OR numbers so to speak).

P.S. To be a bit more concrete. Imagine the different between "concatenation" and "addition by 1". Both could be seen as operation on strings of course. But still "addition by 1" would be a bit complicated when translated in purely string manipulating language.

 

[fbs7]

I think 5-th degree polynomials would fall into category of algebraic numbers (at least if the coefficients are rational) and hence into domain of computable numbers (assuming the "decimal expansion" def. here). I suppose one could use any "approximation methods" of solution (that are in fact usually implemented on actual computers I think) that can calculate the decimal positions to arbitrary high accuracy.

Correct, so the approximation method can calculate any digit of a root of a polynomial, and the program that calculates that is indeed limited in the size of the code, but it will be unbound in memory, because the numbers involved in the calculations become bigger and bigger. So, if we want to calculate a root of a generic polynomial with 10¹⁰⁰ digits we'd need to use calculations involving several numbers with 10¹⁰⁰ digits, and the memory for such computer would bigger than the Universe (and the variables involved would be bigger than the output string).

I have no idea if the Kolmogorov size criteria thingie includes both code and memory, but if it involves memory then such calculation would seem suspiciously close to meeting Kolmogorov's criteria for accepting as random something that we know is deterministic.

And I don't even want to start wondering about programs that we don't know if they stop or not. Say that we write a program that calculates X and then prints L = "Hilbert Conjecture is " + X. We have no idea if that will print "is true" or "is false". So, I know that the string "Bananas are yellow" is not random, but we don't know the value of the sequence L, and we don't know if we can write a program (whatever the size) that calculates that. So if we can't write that program, then that string is random per Kolmogorov - but then if we ever find a way to calculate that, then it won't be random anymore, meanwhile it seems absurd to say the value of a mathematical hypothesis is random whenever we don't know. Holy moshes, this gives me headaches - darn you Kolmogorov, taking away my sleep!

 

[SSequence]

Correct, so the approximation method can calculate any digit of a root of a polynomial, and the program that calculates that is indeed limited in the size of the code, but it will be unbound in memory, because the numbers involved in the calculations become bigger and bigger. So, if we want to calculate a root of a generic polynomial with 10¹⁰⁰ digits we'd need to use calculations involving several numbers with 10¹⁰⁰ digits, and the memory for such computer would bigger than the Universe (and the variables involved would be bigger than the output string).

The abstract definition of a program always means "infinite memory". All "real world" programs are of course really finite automatons in a sense (unless we somehow assume ability to attach bigger and bigger memories as required). But usually thinking about them in a abstract way (like an idealised program) is often quite helpful.

 

[Mark44]

Yes, I understand this. In the same way basically we could take any "positive number" to be a regular expression of form:
(1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)*
where the alphabet is obviously the set {0,1,2,3,4,5,6,7,8,9}.

We could, but we don't need to. Any positive number, or for that matter, any negative number or floating point number can be represented by a string of 0s or 1s. At heart, any data in a computer is composed of binary strings.

 

[jbriggs444]

We could, but we don't need to. Any positive number, or for that matter, any negative number or floating point number can be represented by a string of 0s or 1s. At heart, any data in a computer is composed of binary strings.

Early in a course in the Theory of Computing, one would encounter a number of basic proofs of equivalence^(*). Among these are proofs that Turing Machines running on a binary alphabet have power equivalent to Turing Machines running on arbitrary alphabet sizes. Or with an arbitrary number of tapes. Or with one way unbounded tape, etc. Or that an arbitrary TM can be simulated by a fixed finite Universal Turing Machine that is provided with a description of an emulated TM on input tape.

(*) Equivalent in the sense that if there is a TM of the one sort that can solve a given problem, there is also a TM of the other sort that can also do so.

 

[fbs7]

The abstract definition of a program always means "infinite memory". All "real world" programs are of course really finite automatons in a sense (unless we somehow assume ability to attach bigger and bigger memories as required). But usually thinking about them in a abstract way (like an idealised program) is often quite helpful.

Ah, thank you!

 

[rekoj]

In laymans terms i think random means that there is no exact pattern to follow thus there is no mathematical function that could describe the phenomena except the phenomenon being the function itself which means no shorter description exists than what it is. If one considers that universe is random then trying to put it in theory seems only possible as what it is here and now imo.

 

[SSequence]

In laymans terms i think random means that there is no exact pattern to follow thus there is no mathematical function that could describe the phenomena except the phenomenon being the function itself which means no shorter description exists than what it is.

I do not think this complies with compressibility based definition (given in wiki link in post#74) [... though I think I understand what you are trying to say ... you are equating "random" with "non-deterministic" in a sense]. One would easily give finite descriptions of functions which are simply not compressible. [but then there is a question of what ought to count as a description ... but I want to avoid that]

 

[FactChecker]

In laymans terms i think random means that there is no exact pattern to follow thus there is no mathematical function that could describe the phenomena except the phenomenon being the function itself which means no shorter description exists than what it is. If one considers that universe is random then trying to put it in theory seems only possible as what it is here and now imo.

As a working definition, this would have a problem with something that combines a very predictable part with a truly random part. Suppose that $\{a_n\}$ is a truly random sequence of numbers between 0 and 1. The derived sequence, $\{n+a_n\}$ would be impossible to create even though it would is easy to compress (my definition is a compression). It would not be considered random for practical use.

 

[SSequence]

As a working definition, this would have a problem with something that combines a very predictable part with a truly random part. Suppose that $\{a_n\}$ is a truly random sequence of numbers between 0 and 1. The derived sequence, $\{n+a_n\}$ would be impossible to create even though it would is easy to compress (my definition is a compression). It would not be considered random for practical use.

I am having some difficulty understanding what you are saying. If you assume the sequence $\{a_n\}$ is not compressible (beyond a constant number), then wouldn't it be possible (at least under some circumstances) that $\{n+a_n\}$ is also not compressible? Generally speaking, I do not see any obvious way to give short programs for computing the terms of latter sequence (starting from blank), when we don't have short programs for computing terms of the former sequence? So it seems that such an assertion would need a generic justification?

But then again, maybe I have missed something since I am not fully familiar with this topic.

Or perhaps your premise for the above statement is a little different.

 

[FactChecker]

I am having some difficulty understanding what you are saying. If you assume the sequence $\{a_n\}$ is not compressible (beyond a constant number), then wouldn't it be possible that $\{n+a_n\}$ is also not compressible?

It wouldn't be completely compressible. The integer parts can be compressed, but the $\{a_n\}$ part can not.

 

[SSequence]

My feeling is that, quite likely, there are already quite general theorems in the field of computable randomness that cover the case mentioned above (and probably much more).

P.S. The identity function $n \mapsto n$ should definitely be compressible, somewhat trivially (since we can give very basic demonstrations of small programs computing very large numbers ... hence going outside of the constant range required by definition).

Also, in a similar way, all computable functions that at least grow faster than some very basic rate (say $n \mapsto 2n$) should also be compressible (should be fairly easy to see I think).

 

[fbs7]

These criteria blow my mind. Say that I have a 1,000,000-bytes string that I can compress to 1,000 bytes using zip compression; so, great, I know for sure this is not random.

Now say I have a 1,000,000-bytes string that whatever algorithms I try, I cannot compress. Then I assume it's random. But then tomorrow someone invents some super-fractal-evolving-zop algorithm, that manages to compress that to 900,000 bytes. Now the same string is no longer random. It seems odd to me that a mathematical criteria would be true one day and false tomorrow because someone in Alpha Centauri invented a smart algorithm...

 

[jbriggs444]

These criteria blow my mind. Say that I have a 1,000,000-bytes string that I can compress to 1,000 bytes using zip compression; so, great, I know for sure this is not random.

Now say I have a 1,000,000-bytes string that whatever algorithms I try, I cannot compress. Then I assume it's random. But then tomorrow someone invents some super-fractal-evolving-zop algorithm, that manages to compress that to 900,000 bytes. Now the same string is no longer random. It seems odd to me that a mathematical criteria would be true one day and false tomorrow because someone in Alpha Centauri invented a smart algorithm...

The mathematical criterion did not change. An algorithm "exists" whether it is known or not.

There is also a minor nit. If you want an objective measure of the compressibility of a particular string, you have to count the size of the compression algorithm along with the size of the compressed string. Anybody and his brother can compress a specific 1,000,000 byte string using a custom built 2,000,000 byte compression tool tuned for that string. That motivates the use of a minimal programming environment (e.g. a small Universal Turing Machine) if one is trying to define these things.

Suppose that we have two competing definitions for randomness/compressibility, you with one using your programming environment and me with one using my programming environment. If I can write an emulator of size n for your environment using my environment and if you can write an emulator of size m for my environment using your environment then (with a few more reasonable assumptions) there can only be n+m difference between our two measures of compressibility for any given string.

[Maybe it's max(n,m) -- it has been a while since I glanced at that result and said "oh, that makes sense"]

 

[fbs7]

The mathematical criterion did not change. An algorithm "exists" whether it is known or not.

Ah, I see! Good point!

Now, how about this question; say that P is the set of all possible programs for some given machine; P is certainly infinite. Then for a certain string s we want to consider algorithms p ∈ P whose size(p) < size(s); we don't want to consider algorithms that are too big. Even so, the number of algorithms will be immense; if that string is 1,000,000 bytes, then the programs cannot be more than say 500,000 bytes, therefore, that will be up to 256^500,000 programs, or 10¹⁰⁶. Then how to prove that among that gazillion of programs there isn't any program that will compress that string to 500,000 bytes.

This criteria seems very interesting, but I suspect the application of it may be challenging at best! I'm so happy I didn't become an Information Theory guy, because my poor old brain would be fried many times in the first week!

 

[jbriggs444]

Then how to prove that among that gazillion of programs there isn't any program that will compress that string to 500,000 bytes.

In general, it is not a solvable problem. Are you familiar with the halting problem? There is no general way to tell which of those programs compute anything at all.

 

[fbs7]

Right; I wonder what's the benefit of the compressibility criteria thingie, other than being an interesting statement.

Man, this random string stuff is a tough cookie to crack!

 

[FactChecker]

The compressibility criteria is a rather profound insight that allows one to immediately say that pseudorandom generated numbers are not random no matter what statistical tests they pass. So, although proving a sequence is random may still be challenging, proving that some sequences are not random can be done formally. It also allows one to say that replaying a recorded sequence of random numbers does not make the sequence nonrandom, even though the sequence is determined and repeatable.

However, that definition of random does not address the statistical properties of the sequence. We are almost always more interested in the distribution and certain statistical properties than we are in pure randomness. (There are some exceptions.)

 

[Hornbein]

Having a masters degree in probability and statistics, I can answer this question with authority. I can't be bothered to read this whole thread, so forgive me if I'm redundant.

Probability was axiomatized by Kolmogorov in 1950 or so. Probability is the study of normed measure spaces. There is nothing random about the math that is used to predict probabilities. One can do the math with no concept of probability at all if one so wishes. It can of course be applied to random processes, but like all math the responsibility for the validity of such an application lies with the applier, not the mathematician.

It doesn't help that "random" often implies a uniform distribution. Things that have a 1% chance of going wrong aren't considered random. You just have to keep that in mind.

In my opinion for the most part "random" means "unpredicatable." It is subjective.

However it seems possible to prove more, that some things can never be predicted, and are hence essentially or truly random. Sometimes but not always this is what physicists mean when they say "random."

If you want to prove that something will never be predictable, then you have to show that if you can predict it then some contraction arises. Perhaps Conway and Kochen succeeded in doing that with quantum spin in their Free Will Theorem. Arguments that the spin of entangled quantum particles cannot be used to communicate are of this sort. If you could communicate in that way then the concept of causality falls apart.

I would say that presidential elections are random. But this is not how the word is commonly used. We think -- rather dubiously, say I -- that there is some reason that so-and-so won. So this sort of thing is excluded. More often "random" is something that is done for incomprehensible reasons, or a mechanical system that is not well understood. But maybe tomorrow such reasons or systems will be better understood. Then they will no longer be random to a person who understands it. But it will be random to someone who doesn't. A good example is the magnetic field reversals of Earth. Today they are random. But sooner or later I believe they will become at least somewhat predictable. Or the orbit of the planets. They were random until Ptolemy came up with his epicycles.

I have personal experience with this. I have some videos I made on Youtube. The viewership is quite random day to day. But recently I looked at some graphs of views over the last two years. One was a linear, another exponential, and a third logarithmic. It was amazing how close the curves fit what I had thought were isolated blips. I feel I can confidently predict that these trends will continue. Then as well some of the vids had viewership graph lines that wiggled around. Random.

Is the CMB random or not? Hard to say, hard to say. So I don't worry about this issue much. I just use my simple definition, that "random" and "unpredictable" are the same, and let others discuss definitions.

 

[fbs7]

Wow, what an impressive post! Thank you so much for it - I'll definitely re-read it several times, as it refers to several concepts I'm not familiar with! Thank you!

Let me ask a related question... say that Civilization 9 From Outer Space decides to announce themselves by sending a radio signal that is beyond any possibility of confusion with any natural process. So they send say 100 billion trillion bits of the number pi in binary. Their thought is... "the chance of any natural process to generate pulses that are the same as the number pi with 100 billion trillion bits is nil, and any Civilization 9 child with IQ of 1 billion will recognize pi in a blink!".

We know that the bits of pi in binary are not random at all; but it passes our random tests as random, and as we don't have an IQ of 1 billion we can't really distinguish that signal from random noise. So, in that case we may not be able to distinguish an intelligent, designed, procedural, calculated and predictable sequence from random noise.

The question is... where's the mathematical gap in scenarios like this? Once you know the context of a sequence (say the algorithm or a "meaning") it's easy to know if something is not random. But context is not mathematical, so short of having some additional information about a sequence or being lucky in compressing it, in general it seems to be an impossible problem of separating if something is truly random or is just generated by some mechanism that we don't understand - that would be my guess.

ps: Now extend the scenario to say alpha decay. We can get timings of alpha decay, and they may seem completely random to us... but maybe there is an underlying deterministic process for alpha decay, but it's too complicated for our low IQ and "random" there just means we don't really know the rules that control it?

 

[FactChecker]

@Hornbein , Good post. I have a couple of thoughts.

It doesn't help that "random" often implies a uniform distribution. Things that have a 1% chance of going wrong aren't considered random.

One field where very small probabilities are studied is in reliability engineering with tools like fault trees. They often study rare events that have catastrophic consequences.

In my opinion for the most part "random" means "unpredicatable." It is subjective.

I am not sure that I would call this subjective. I agree that the interpretation of "random" is often dependent of the amount of information available. But, given a certain set of information, either there are more than one possibility to guess about or the result is predictable. That would make it objective, but dependent on the information available.

There are common examples where the lack of information is key to treating something as random. Suppose a coin is tossed, caught, and the result is covered. After that, there is nothing physically random about the result -- it has already happened and the result is determined but unknown. If we try to guess the result, we still treat this as a random process.

 

[sysprog]

@Hornbein , Good post. I have a couple of thoughts.
One field where very small probabilities are studied is in reliability engineering with tools like fault trees. They often study rare events that have catastrophic consequences.I am not sure that I would call this subjective. I agree that the interpretation of "random" is often dependent of the amount of information available. But, given a certain set of information, either there are more than one possibility to guess about or the result is predictable. That would make it objective, but dependent on the information available.

There are common examples where the lack of information is key to treating something as random. Suppose a coin is tossed, caught, and the result is covered. After that, there is nothing physically random about the result -- it has already happened and the result is determined but unknown. If we try to guess the result, we still treat this as a random process.

And even if it's an unfair coin, if I don't know which way it's biased, my odds of guessing correctly or incorrectly which way up it is are still 50% each.