Re: Probability, compressible sequences: Backgrounds

Industrial One schrieb:
On Mar 7, 1:05 am, Thomas Richter <t...@xxxxxxxxxxxxxxxxx> wrote:
Hi folks,

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

A specific sequence can be random-appearing.

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. (-:

So long,
Thomas

.

Relevant Pages

  • =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>Sure a protein string could be generated from by organic Turing machine ... >>For example, a proteins sequence, like a lactase sequence, could indeed ... > proper compression. ... >>The notion of randomness is dependent upon chaos. ...
    (talk.origins)
  • Probability, compressible sequences: Backgrounds
    ... noise is caused simply because people do not use adequate definitions ... A "specific sequence" cannot be random. ... frequencies of the symbols, and for a well defined random process, I ... The *average* output length of your compression ...
    (comp.compression)
  • Re: =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... There is no compression possible, ... compressed expression is shorter than the expressed string), ... makes no sense to ask whether the DNA-base sequence is shorter than the ... > language system code needed to compress and decompress the sequence. ...
    (talk.origins)
  • Optimal encoding of monotonic integer sequences
    ... For the linearly increasing sequence these ... Here you will encode integers not via the fixed length of s bits (which ... can trade off some compression optimality for speed by breaking ...
    (sci.math)
  • Re: Theoretical Limits for Compression Algorithms and Random Sequences
    ... there isn't a compression algorithm that provides compression for any ... If our algorithm just compresses a few range of the all possible ... The "random" sequence lies over the majority of the input space. ... You forget - compression functions don't on the whole compress. ...
    (comp.compression)