3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I'm wondering why you cut-and-paste the first part of your question from here without referring to it? $\endgroup$ – Peter K. Sep 3 '15 at 22:36
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I think your answer is a bit imprecise; you're mixing the concepts "real-valued random variable" and "continuous random variable". The important concept here is whether the RV is discrete, and not the specific values it can take. For example, if a RV can take values $\lbrace \sqrt{2},\sqrt{3} \rbrace$, it is real-valued, but you can find its entropy. $\endgroup$ – MBaz Sep 8 '15 at 16:54
  • $\begingroup$ @MBaz... yeah. Shouldn't have written that when I was so tired, will rephrase. $\endgroup$ – Marcus Müller Sep 8 '15 at 17:27
  • $\begingroup$ @MBaz rereading everything, I'm not quite sure I get your point... I never claim the discrete variable can't take real values. $\endgroup$ – Marcus Müller Sep 8 '15 at 17:29
  • $\begingroup$ @MBaz: nevermind. First sentence. $\endgroup$ – Marcus Müller Sep 8 '15 at 17:29
  • $\begingroup$ @MarcusMüller: Thank you for your reply, I had to do a thorough reading before I could get back to you. So, I learned that the entropy or entropy rate of a random bit sequence = 1 and from your answer the entropy of continuous random variable is $\infty$. So, in communications do we prefer a finite number = 1 or an infinite entropy? If entropy = $\infty$, it means we are less certain about what the information will be next. Whereas if entropy =1, then there is no information conveyed. $\endgroup$ – Srishti M Sep 16 '15 at 21:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Based on MarcusMiller & your reply, we prefer binary encoding or digital transmission. But, the entropy or entropy rate of a random bit sequence = 1 & entropy of continuous random variable is $\infty$. If entropy = $\infty$, it means we are less certain about what the information will be next. Whereas if entropy =1, then there is no information conveyed. All this is confusing. What is the desired entropy preferred in communication--$\infty$ or 1 & what is this the reason for bit based communication/digital if entropy =1? Can you please shed some light + references if any? $\endgroup$ – Srishti M Sep 16 '15 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.