If you understand information in the information theoretic sense, the
entropy of a source is the average amount of information you get from
the source per letter. Or to be precise, entropy is the expected value
of information. Information, however, is probably not what you believe
what it is. It is simply the logarithm of the symbol probability. That
is, the average number of yes-no questions you need to guess the
message. In the framework of this "riddle game", information (as in
entropy) is the information as you know, but only then. It is *not* the
information as you may believe it is.

Mok-Kong Shen wrote:

Is the following sequence of head/tails from coin flips random?


H, H, H, H, H

It doesn't look very random, but randomly occurs about 3% of the time.
Any finite sequence (over a finite alphabet) can be generate
randomly. It is different for an infinite length sequence.

Question: how do you know that a given source is or is not random?

You don't. You simply *assume* that, and then design a model that
generates sequences that look like the ones you want to compress. And
from that model you compute the entropy.
[snip]

Thomas Richter ha scritto:

Well, we now enter the realm of "existence or not". Basically,
Kolmogorov complexity exists in the same sense dragons exist. As an
abstract concept. You cannot potentially measure it, or design an
algorithm for it, you can only use it as a mathematical abstractum to
prove theorems about it.



Kolmogorov complexity exists in the same sense dragons exist and this is
true for every mathematical concept.

I can effectively measure a Kolmogorov complexity of a finite bit string
in a real existing universal machine . Such measure can be wrong .

But if I put 2 balls into a box and then I put another ball into the
same box by mathematic concept I can say into the box there are 3 balls.
Are you sure ? Why are you sure there are 3 balls into the box and that
the measure of Kolmogrov complexity are wrong ?

So the Kolmogorov complexity exist in the realm like every mathematical
abstract concept exist in the realm.

Thomas Richter wrote:

If you understand information in the information theoretic sense, the
entropy of a source is the average amount of information you get from
the source per letter. Or to be precise, entropy is the expected value
of information. Information, however, is probably not what you believe
what it is. It is simply the logarithm of the symbol probability. That
is, the average number of yes-no questions you need to guess the
message. In the framework of this "riddle game", information (as in
entropy) is the information as you know, but only then. It is *not*
the information as you may believe it is.

I like to return to what I said previously regarding knowledge
and resources. I mean the information carried by a text string
(physically present in characters or bits) is inherently dependent
on a person's knowledge and resources.

As a rather trivial example:
If I get a sentence in a language, say Greek, that I don't know, it
means for me virtually nothing. If, on the other hand, I had learnt
Greek very well, I get the full information out of it.

Thomas Richter wrote:
Mok-Kong Shen wrote:

Is the following sequence of head/tails from coin flips random?


H, H, H, H, H

It doesn't look very random, but randomly occurs about 3% of the time.
Any finite sequence (over a finite alphabet) can be generate
randomly. It is different for an infinite length sequence.

Question: how do you know that a given source is or is not random?

You don't. You simply *assume* that, and then design a model that
generates sequences that look like the ones you want to compress. And
from that model you compute the entropy.
[snip]

Question: How do I in practice design the model? Is there a standard
"recipe" for that or many different models could be designed (depending
perhaps on one's ingenuity)?

If the latter, which one of the many
candidates should one choose? In particular, which model would you
propose for the sequence in the present case and why?

Thomas Richter wrote:
Mok-Kong Shen wrote:
[snip]
Should one
investigate the construction/mechanism of software/hardware instead?

For Shannon entropy, one should. It depends on the *construction* of
the sequence, not the sequence.

What should one do, if the "consturction" is unknown or practically
unavailable in required details?

As an example in natural language:
If I see a sentence on the internet, it could be written by a human,
but it could as well be the result of some sophisticated automatic
natural language processing system or maybe even the chance product
of the monkey of the British Museum? (BTW, I once saw paintings by
apes that were hard to distinguish from works from artists of certain
schools.)

Thomas Richter wrote:
Mok-Kong Shen wrote:

Excuse me for not yet fully understanding you. Under the correct
definition of the entropy estimate you gave above and assuming that
the range of, say, 1.0 - 1.5 bits per character is ok, wouldn't I
still get the same sort of paradox, in that a short string is shown
to be equivalent (one being obtainable from the other) to a very
long string?

You mean, in the book example? Entropy doesn't measure whether
"information" (in the laymens' sense) is "equivalent". It doesn't care
for this. You still seem to confuse "entropy" (a strictly defined
term) with "the kind of stuff I learn when I would read the book",
which is *not* the type of information Shannon talks about. Shannon
talks only about random sources, and their information content per
symbol. Not about a high-level "content-type" like entropy.

There is, I think, at least one problem here when natural language
is concerned. How correct is the assumption that human utterance
is a random source?

You wrote in the other post that one needs to
know the "construction". Would one need eventually details of the
brain or the anatomy of the vocal tract etc.?

If your model is "I have a huge collection of books and I have a
random source that picks one of them at random", then you can define
the entropy of said source. Then it doesn't matter whether you
identify the books by title or ISBN (provided the former is unique).
This is a *different* problem from "I want to read the book and
understand what the author talks about", which entropy cannot answer.
It takes a human, and side-conditions (knowledge about the world, the
period the author was writing the book, your environment and feelings
how you associate the book contents with your personal life etc) to
define that - and that's a much harder problem.

OK, let me do as you said: I randomly pick the book and generate
randomly two numbers which happen to come out as 100 and 200. I get,
as before, two text strings, one short and one long. Do they have
the same entropy?

Thomas Richter wrote:
Mok-Kong Shen wrote:

Richter wrote that Kolmogorov complexity caanot be well-defined
on finite messages. That implies in my understanding that this
measure is only of high theoretical interest but unfortunately can
never be applied to practical strings that occur in texts or
discourse. In fact, I remember to have heard that there isn't
todate any "practical" computation of the value of Kolmogorov
complexity of real-life strings.

Even worse. It is not even so that it cannot be defined practically or
measured practically. One can even *prove* that there is no computer
algorithm that could possibly measure it. Thus, it is impossible to
define it in practical terms.

BTW, I now vaguely (not very sure) remember on the other hand to have
once read somewhere that Kolmogorov developed a mathematical concept
of complexity for sequences of finite lengths. Does that affect what
you said above or was it simply because of my faulty memory?

You can define the Kolmogorov complexity on finite sequences *given*
that you have a specific Turing machine. It is the size of the shortest
program *on this machine* that regenerates the message.

The problem is that this definition is always relative to the machine,
*unlike* - and this is the important part - you define it on infinite
strings. *Then* the machine doesn't matter anymore.

The problem with the finite-sized input - and why it makes little sense
there - is simply that for every finite sized message you can define a
Turing machine which generates this message simply by a one-step
program: Put the message into the state-apparatus of the Turing machine.
(Aka: The "Lena compress" version of Kolmogorov complexity. True,
working, but useless).

Independence from the machine on infinite messages:

This is simply because any Turing machine can emulate any other Turing
machine by a finite-sized program, and the contribution of a
finite-sized program to an infinite string doesn't matter.

You are still on the wrong track. This is *not* the entropy we talk
about. For the entropy we talk about, we *do* know the alphabet the
message is made of, and we do know the probabilities and their
dependencies. It is *not* about interpreting the message, only getting
the symbols it is made of. The symbols could be Chinese, and all you get
is a table of all possible symbols in chinese, and their (conditioned,
unconditioned...) probabilities, i.e. a description of the source (a
chinese monkey, if you like).

Thomas Richter wrote:

You can define the Kolmogorov complexity on finite sequences *given*
that you have a specific Turing machine. It is the size of the
shortest program *on this machine* that regenerates the message.

The problem is that this definition is always relative to the machine,
*unlike* - and this is the important part - you define it on infinite
strings. *Then* the machine doesn't matter anymore.

The problem with the finite-sized input - and why it makes little
sense there - is simply that for every finite sized message you can
define a Turing machine which generates this message simply by a
one-step program: Put the message into the state-apparatus of the
Turing machine.
(Aka: The "Lena compress" version of Kolmogorov complexity. True,
working, but useless).

Independence from the machine on infinite messages:

This is simply because any Turing machine can emulate any other Turing
machine by a finite-sized program, and the contribution of a
finite-sized program to an infinite string doesn't matter.

As layman I rather doubt that letting any kind of machine (real or
theoretical) to work on an infinite string could have a sense.
I mean by definition of "infinite", the work could never get to an
end (no matter what the processing speed is) and thus no result
would ever be available.

Mok-Kong Shen wrote:
Thomas Richter wrote:

You can define the Kolmogorov complexity on finite sequences *given*
that you have a specific Turing machine. It is the size of the
shortest program *on this machine* that regenerates the message.

The problem is that this definition is always relative to the
machine, *unlike* - and this is the important part - you define it on
infinite strings. *Then* the machine doesn't matter anymore.

The problem with the finite-sized input - and why it makes little
sense there - is simply that for every finite sized message you can
define a Turing machine which generates this message simply by a
one-step program: Put the message into the state-apparatus of the
Turing machine.
(Aka: The "Lena compress" version of Kolmogorov complexity. True,
working, but useless).

Independence from the machine on infinite messages:

This is simply because any Turing machine can emulate any other
Turing machine by a finite-sized program, and the contribution of a
finite-sized program to an infinite string doesn't matter.

As layman I rather doubt that letting any kind of machine (real or
theoretical) to work on an infinite string could have a sense.
I mean by definition of "infinite", the work could never get to an
end (no matter what the processing speed is) and thus no result
would ever be available.

You can still get the next output symbol, in the same sense that you can
get the next symbol from the digits of Pi. Pi can be represented as an
infinite decimal fraction, yet it makes sense to speak about Pi in
total. That is, it is at least "potentially infinite" in the sense that
you can always get the next symbol, and it never terminates, and the
length is not finite ad-hoc.

Thomas Richter wrote:

You are still on the wrong track. This is *not* the entropy we talk
about. For the entropy we talk about, we *do* know the alphabet the
message is made of, and we do know the probabilities and their
dependencies. It is *not* about interpreting the message, only getting
the symbols it is made of. The symbols could be Chinese, and all you
get is a table of all possible symbols in chinese, and their
(conditioned, unconditioned...) probabilities, i.e. a description of
the source (a chinese monkey, if you like).

I have a layman's question here: In the character strings of
natural languages there are more or less strong correlations,
as the statistical data on digrams and n-grams show. If I
don't err, such correlations are not considered in Shannon's
formula.

You can still get the next output symbol, in the same sense that you
can get the next symbol from the digits of Pi. Pi can be represented
as an infinite decimal fraction, yet it makes sense to speak about Pi
in total. That is, it is at least "potentially infinite" in the sense
that you can always get the next symbol, and it never terminates, and
the length is not finite ad-hoc.

OK, but when do you take the result from the machine?

At the
moment you take the result, only a finite number of symbols
have been processed. So you "always" get results from a finite
string, never from an infinite string, although you may choose
to have that finite string to be as long as you like, if you
spend correspondingly long time.

Mok-Kong Shen wrote:

I have a layman's question here: In the character strings of
natural languages there are more or less strong correlations,
as the statistical data on digrams and n-grams show. If I
don't err, such correlations are not considered in Shannon's
formula.

There is no "the formula". There is an n-order entropy definition, and
that definition would of course capture the correlation. Zero-order
entropy, of course, does not. Or, to put it differently, if you have a
source with correlation, increasing the order of the entropy measurement
will decrease the entropy. Or rather, if you have an nth-order model,
you should measure entropy as n-th order entropy, obviously.