What is the entropy for these cases?

Question

This question stems from an article,

"Entropy estimation of symbol sequences" download link

where the abstract mentions the need for using symbols in information theory.

Random chains of symbols (zeros and ones or characters) $s_1, s_2,\ldots,$ drawn from some finite alphabet appear in practically all sciences. Examples include spins in one-dimensional mag- nets, written texts, DNA sequences (here symbols are alphabets), geological records of the orientation of the magnetic field of the earth, and bits in the storage and transmission of digital data.

The paper presents technique for finding the entropy of symbols. My Question is that if entropy of symbols is important then what about the entropy of real valued numbers? From the perspective of entropy, is there a proof or some information in text where it provides information that the entropy of random symbols is greater or lesser than the entropy of real numbers.

Q1: In other words, what would be the entropy of random variables having binary values and entropy of real valued random variables? A fair coin takes 2 values -0/1 with equal probability and its entropy is 1 bit. So, is 1 bit the maximum entropy? Would entropy of binary random variables be less or more than entropy of real valued random variables and how to show?

So, I would like to know if there is a proof or material from which it can be inferred if the entropy of characters is lesser/ greater or same with the entropy of real numbers.

Q2: I want to know why symbols are used in coding and other applications such as storage from the viewpoint of entropy and information theory.

Answer 1

The entropy $H(X)$ of a continuous random variable $X$ is infinite. Proof is trivial (note that we can, without loss of generality, use the natural logarithm, since any other logarithm is the same but with a factor: $\log_b(x) = \frac 1{\ln(b)}\ln(x)$):

\begin{array} \\H(X) &= E\{I(X)\}\\ &= \int\limits_{-\infty}^{\infty}{-\ln\left(P(X=x)\right) dx} \end{array}

The point here is that for any really continuously distributed random variable, the probability that a specific real value gets "hit" is $P(X=x)\equiv 0 \,\forall x$, and hence, the information contained in that event happening would be infinite. You hence cannot directly compare discrete alphabets with dense intervals (such as the whole $\mathbb R$).

Hence, people invented differential Entropy. For your real-valued (=1-dimensional) case, this is nothing but the obvious:

$$h(x) = \int\limits_{-\infty}^{\infty} f(x)\log_b\left(f(x)\right)dx \text{,}$$ with $f$ being the continuous probability density function of $X$.

Now, all you need to compare your discrete case with the continuous is model the discrete PDF for the alphabet $\mathbb X$

$$ f_\text{discrete}(x) = \sum\limits_{x_i\in\mathbb X} \delta(x - x_i)P_\text{discrete}(x_i) $$

$\delta$ is the dirac function.

Caveat not everything you know about the discrete entropy applies to differential entropy. Read the Wikipedia Article!

Answer 2

Adding a bit of detail to Marcus' answer:

• Your question is about the "entropy of symbols" and the "entropy of real numbers". In information theory, only sources have entropy. A source has an alphabet, and each "letter" or symbol from the alphabet has a certain probability, and carries a certain amount of information.

• Think of a source as a black box with a button. Every time you press the button, it produces a symbol. In many textbook problems the source is fully described, but in practice, you often don't know what the source alphabet is and what the symbol probabilities are. This is where "entropy estimation" comes in: basically you push the button many times, keep notes about the symbols that appear, and try to guess the entropy.

• Note that this problem is more common than you may think: nobody knows the entropy of a source that produces all possible written language, for example. This is why entropy compressors, such as the Huffman algorithm, do some form of entropy estimation.

• Shannon's formula for entropy assumes that the source alphabet is discrete. The case where it is continuous is covered in Marcus' answer. It doesn't matter if the symbols are real numbers, what matters is the continuity (or lack thereof) of the source alphabet.

• Your second question is too open-ended to give a simple answer, but the idea is that you want to come up with a binary encoding to the source symbols. A good encoding assigns less bits to the more probable symbols.