Hi folks,

A "specific sequence" cannot be random. And as such, as long as you know

your sequence, you can compress it. Actually, to zero bit, as you know

Second misunderstanding: "RAD" or "random process" does not imply that
the probabilities of all symbols of the random process are equal. That
is, in fact, the boring case as it is easy to show that you cannot
compress this (i.e. for any compression device, the *average* output
length is equal to the input size, taking the number of experiments and
the size of the sequence to infinity). Furthermore, in no way the
probability of the next symbol need to be independent of the symbols
before (i.e. there is no need for the process to be memory-less). This
is again the "boring case". Compressors work because they model the
input source by a random process that *does* have memory. And this is a
good model for text, language, programs, images... "Good" as in "it does
work". We "do not have" a random device that generates symbols *exactly*
as in text/speech/images... etc. But "it's close enough for the purpose
of compression to assume it" - that is, "a model".

On Mar 7, 1:05 am, Thomas Richter <t...@math.tu-berlin.de> wrote:
Hi folks,

A "specific sequence" cannot be random. And as such, as long as you know

A specific sequence can be random-appearing.

your sequence, you can compress it. Actually, to zero bit, as you know

Not really... if the sequence is random-appearing, without redundancy/
patterns, how do I compress it to zero bit?

Second misunderstanding: "RAD" or "random process" does not imply that
the probabilities of all symbols of the random process are equal. That
is, in fact, the boring case as it is easy to show that you cannot
compress this (i.e. for any compression device, the *average* output
length is equal to the input size, taking the number of experiments and
the size of the sequence to infinity). Furthermore, in no way the
probability of the next symbol need to be independent of the symbols
before (i.e. there is no need for the process to be memory-less). This
is again the "boring case". Compressors work because they model the
input source by a random process that *does* have memory. And this is a
good model for text, language, programs, images... "Good" as in "it does
work". We "do not have" a random device that generates symbols *exactly*
as in text/speech/images... etc. But "it's close enough for the purpose
of compression to assume it" - that is, "a model".

I don't see how these descriptions satisfy those common
characteristics of RAD. Unless the approximate 50:50 strings really
make up a majority of all possible combos of size N.

I don't know what this should be. It's a non-standard term, and, as you've seen
from all the discussions, it's ill-defined. What "appears" random is in the
eye of the beholder. I don't care, and neither does a compression algorithm.
It applies a model to a sequence, but whether this sequence compresses well
or not is not a question of whether it appears random or not, but whether
it fits to the statistical model of the compressor. The question is, is
this a typical sequence for the random model you imply. *That* is a useful
definition.

your sequence, you can compress it. Actually, to zero bit, as you know

Not really... if the sequence is random-appearing, without redundancy/
patterns, how do I compress it to zero bit?

Entropy and compression is about communication channels. If you know the sequence,
you don't need to communicate it from somewhere, you just write it down. Your
information channel requires exactly zero bits of capacity to do that, so it's
compressed down to zero.

Second misunderstanding: "RAD" or "random process" does not imply that
the probabilities of all symbols of the random process are equal. That
is, in fact, the boring case as it is easy to show that you cannot
compress this (i.e. for any compression device, the *average* output
length is equal to the input size, taking the number of experiments and
the size of the sequence to infinity). Furthermore, in no way the
probability of the next symbol need to be independent of the symbols
before (i.e. there is no need for the process to be memory-less). This
is again the "boring case". Compressors work because they model the
input source by a random process that *does* have memory. And this is a
good model for text, language, programs, images... "Good" as in "it does
work". We "do not have" a random device that generates symbols *exactly*
as in text/speech/images... etc. But "it's close enough for the purpose
of compression to assume it" - that is, "a model".

I don't see how these descriptions satisfy those common
characteristics of RAD. Unless the approximate 50:50 strings really
make up a majority of all possible combos of size N.

Then probably your definition of "random" is screwed. (-:

I'm astounded that "random appearing" is such an alien concept around
this joint.

if a sequence passes the K-Complexity test, then it's viable?

The only definitions I got in mind are: a 50:50 bit distribution
(faulty because the data can contain sorted 0s and 1s that can easily
be compressed.)

And a random sequence should not repeat the same byte
value until the other bytes have appeared proceedingly

If I provide 5 examples of random-appearing files, would that be a
qualifiable definition for you?

http://www.zshare.net/download/8619286370d491/

Go ahead, compress 'em if you can.

Hi folks,

since there was enough noise in this group once again, I afraid much
noise is caused simply because people do not use adequate definitions
for the subjects to be discussed here, and it's time to clean up the
mess. Folks, before you discuss, please get some background, really,
even if it only helps to reduce the noise level here.

A "specific sequence" cannot be random. And as such, as long as you know
your sequence, you can compress it. Actually, to zero bit, as you know
what you're talking about, so there's no point in transmitting it in
first place.

"Entropy" and "compressibility" are statements that are not
defined on *specific* sequences, or on "subsequences of specific
sequences", but only on *random processes*. A *process* is something
different than a *sequence*.

By that I mean that, in order to define the terms, I need to have a
device (probably a coin) that generates symbols (head or tail) by an
external trigger (me, dropping the coin). I can measure the relative
frequencies of the symbols, and for a well defined random process, I
must ensure that these frequencies converge to probabilities as the
number of experiments grows to infinity. *This is nothing you can
prove*. It is an assumption you have to make about your device to have
the theory make some sense.

Second, compressibility does not speak about "compressing sequence A or
B". It speaks about "compressing sequences on average generated by a
random device as above". That means, operationally, you run a long
sequence of experiments, using the same device, understanding that it
doesn't change its statistics, and feed the output of each experiment
(each of which generating a lot of symobls) into your compression
algorithm. The *average* (expected) output length of your compression
algorithm, divided by the number of input symbols, is the
"compressibility" - *OF THE RANDOM PROCESS*. Note that I'm not talking
about a specific sequence, this doesn't make sense.

The reason why "compressors work", or rather, the philosophy behind
them, is to model (or rather "misunderstand") the input sequence "as if"
it had been generated by a random process, and build a compressor that
works well *on this* random process. Not on any *specific* sequence.

Second misunderstanding: "RAD" or "random process" does not imply that
the probabilities of all symbols of the random process are equal. That
is, in fact, the boring case as it is easy to show that you cannot
compress this (i.e. for any compression device, the *average* output
length is equal to the input size, taking the number of experiments and
the size of the sequence to infinity). Furthermore, in no way the
probability of the next symbol need to be independent of the symbols
before (i.e. there is no need for the process to be memory-less). This
is again the "boring case". Compressors work because they model the
input source by a random process that *does* have memory. And this is a
good model for text, language, programs, images... "Good" as in "it does
work". We "do not have" a random device that generates symbols *exactly*
as in text/speech/images... etc. But "it's close enough for the purpose
of compression to assume it" - that is, "a model".

Going back to the original statement: It would help a lot if, before you
would start discussing, you would start from a proper definition of
words. I'm not saying that the above one is the "only" or "correct" one,
but a lot of noise here could have been avoided if you would have stated
clearly what you're talking about.

Thanks for reading,

Thomas

A "specific sequence" cannot be random. ... A *process* is something
different than a *sequence*.

The reason why "compressors work", or rather, the philosophy behind
them, is to model (or rather "misunderstand") the input sequence "as if"
it had been generated by a random process, and build a compressor that
works well *on this* random process. Not on any *specific* sequence.

Thanks for reading,
Thomas

Model-complexity is synonymous with "entropy"

A "specific sequence" cannot be random. And as such, as long as you know
your sequence, you can compress it. Actually, to zero bit, as you know
what you're talking about, so there's no point in transmitting it in
first place.

In the compressed sequence you need to insert also the decompressor
otherwise it is trivial.
How can you compress a specific sequence wthin the decompressor to
zero?

"Entropy" and "compressibility" are statements that are not
defined on *specific* sequences, or on "subsequences of specific
sequences", but only on *random processes*. A *process* is something
different than a *sequence*.

I think it is possible ( not only possible but I think it is the only
way ) to speak about "Entropy" and "compressibility" about sequence
indipendently from processes.

I try to reassume your point of view let me know if I misunderstand.

You say that speaking about random sequence is nonsense, you need to
define the process and if the process is random the sequence produced
by the process will be random indipendently from the compressibility
of its serquences.

How can you define a random process?

A coin is a random process? Why?

You use a random process as hypothesis and then using this hypothesis
you define the sequence as random .

You can say ok this sequence is the result of a coin so we know this
is a random process and the sequences will be random but you need to
know that the process is random and to know a process is random you
need to analize its sequences ( yes there are other ways but ...) !

We know the coin flipping is a random process becouse in the past we
analize its sequences and we understand is it about impossible to
predict its result and the sequence is incompressbile.

For this reason I go in the opposite direction I claim that the only
way to define a random process is to identify its sequences as
random , not compressible.

Using the coin as device you can create a random process becouse this
process produce not compressible sequences.
Now you can try to flip a coin and you can give me a sequence
absolutely compressible and claim that it is random.

Using the compressibility principle I must say that process is not
random and this is a mistake but if you know only that sequence the
best claim possible is that the process is not random !
To say that the sequence is random you need to identify its process as
known random process and then you can give the correct answer , but
you need to know a lot of data , more than the amount of the sequence.

For these reason I say we can speak about random sequence, becouse the
only way to identify a process as random is to watch at its sequences.

For these reason I say we don't need to know the process to speak
about random.
And for these reason I claim
Random data is incompressible by definition!

hehe, Thomas got owned.

It allows you to
derive certain results, always hoping that the implicit assumptions you
put into the model fits well to reality, and thus obtaining results that
fit to reality.





If I use a biased coin, the sequence generated by a coin experiment will
very well be compressible, but it is still random. Even a loaded dice
generates random sequences. (More precise: "A zero-order random process
modeling the biased coin does not have maximum entropy"). Just that the
probabilities aren't all equal, but that doesn't change the theory.

Actually, the only reason why we use compressors is that we model data
by random processes whose probability metric is *not* uniform.

Using the compressibility principle I must say that process is not
random and this is a mistake but if you know only that sequence the
best claim possible is that the process is not random !
To say that the sequence is random you need to identify its process as
known random process and then you can give the correct answer , but
you need to know a lot of data , more than the amount of the sequence.

Of course "knowing a process" is a lot more than "knowing one of its
outcomes". That's exactly the point why "processes" are compressible or
not, not "outcomes". And that's exactly the reason why all working
compressors can only compress a *tiny* amount of sequences, namely those
that are outcomes of random processes used for defining the compressor.

Again, please get your concepts cleaned up.

"random" cannot be put into a strict
definition - it doesn't make sense.

Your definition of random is well defined becouse we can know if we
are in random domain or not without uncertainty .
My definition stay in a more practical domain and never give you
certainty ( as I mentioned is possible to make miskate in the
prevision ) but it give to you how much you can believe and you can
not do something better.

I think we can not remove terminology "random" outside mathematical
abstract field becouse we need it.

We need to know how much we can make prevision and if we can make
prevision , this is what random means and we can work starting only on
finite data .

We can also starting from data , choosing an abstract model and here
we can reasoning about Randomness with big "R" without uncertainty but
what we do here is only to move the uncertainty into the model
choosing phase , we are never sure to choose the correct model so at
the end we have the same uncertainty.

Actually, the only reason why we use compressors is that we model data
by random processes whose probability metric is *not* uniform.

... I am interested , can you give me some links?

Using the compressibility principle I must say that process is not
random and this is a mistake but if you know only that sequence the
best claim possible is that the process is not random !
To say that the sequence is random you need to identify its process as
known random process and then you can give the correct answer , but
you need to know a lot of data , more than the amount of the sequence.
Of course "knowing a process" is a lot more than "knowing one of its
outcomes". That's exactly the point why "processes" are compressible or
not, not "outcomes". And that's exactly the reason why all working
compressors can only compress a *tiny* amount of sequences, namely those
that are outcomes of random processes used for defining the compressor.

(tiny... the zip in my pc compress about every files and about with
%50 of ratio . I think it's incredible but I think pheraps I will make
a different thread to speak about this ...)

Again, please get your concepts cleaned up.

I think ( and I hope ) I will never finish to clean up my concepts.

Your interpretation of
"random" cannot be put into a strict
definition - it doesn't make sense.

Yes not so strict but maximal available and it make sense.