0
$\begingroup$

This question already has an answer here:

I have read some books about information theory but I don't have any ideas how can they find the definition of entropy? We have $$H(X)=-\sum_{x\in X}p(x)\, \text{log}\, p (x)$$ X is a discrete random variable.

$\endgroup$

marked as duplicate by qwr, TheSimpliFire, stressed out, Namaste, Parcly Taxel Jul 13 '18 at 13:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ math.stackexchange.com/questions/331103/… $\endgroup$ – Lorenzo Jul 13 '18 at 4:03
  • $\begingroup$ I suggest that you read section 6 on page 10 of Shannons paper. There he explains what properties he wants of a measure of how much choice/uncertainty there is of an outcome and states (with a proof in an appendix) that such a measure must have this form. $\endgroup$ – md2perpe Jul 13 '18 at 18:24
2
$\begingroup$

Well, "finding" the definition of entropy is similar to "finding" imaginary numbers in the sense that they don't really exist; they are just useful quantities that help us understand phenomena around us. Shannon justifies using this "logarithmic measure" in his iconic paper A mathematical theory of communication (available online almost anywhere)

His justification is:

1) In engineering, a lot of things scale logarithmically. (Think decibels)

2) Feels natural (for instance, getting one more punch-card should your information storage, but now you can store a number that is twice as many digits, and number of digits goes logarithmically)

3) Mathematically nice and convenient

Now, you can also prove that they can be derived from some intuitive axioms called Kninchin Axioms.

$\endgroup$
1
$\begingroup$

TL;DR: Entropy is defined this way because this definition is useful.


You don't really "find" the definition of something, you come up with it in order to solve some problem. You can define some function $f(x)=x^2+\sin(x)-\log_{42}(|x|)$ and call it the PHT function, that's not the issue. The real question here is: is this function/quantity useful? How so?

The definition of entropy is natural in the context of information theory because it is tremendously useful for solving problems. Here are some basic examples.

Problem 1

Suppose I have a very large text file, say made up of a billion characters. I want to store it using the smallest number of bits possible, in such a way that no information is lost. How many bits do I need?

Let's say for simplicity that each character in the text file is independently chosen according to some probability distribution. Let $X$ denote the random variable representing a character and $p(X)$ its distribution. Then, a file of $n$ such characters can be losslessly represented by $nH(X)$ bits (if you use log base 2), but no fewer.

Problem 2

Say I am trying to communicate to you across a memoryless channel. I can send some symbols $X$ into the channel and you observe $Y$, where $Y$ is determined according to some conditional probability $p(Y|X)$. How can I manipulate $X$ so that I transmit information to you as fast as possible? In other words, what is the capacity of this channel?

It turns out, the capacity is precisely $$ \max_{p(X)} H(Y) - H(Y|X) $$ bits per channel use (again if you use log base 2).

See https://en.wikipedia.org/wiki/Noisy-channel_coding_theorem


These are some of the most basic problems in information theory. You can see that their solutions make direct use of entropy. This is the true reason entropy is defined this way: it's useful for solving problems.

$\endgroup$
1
$\begingroup$

The entropy measures how much you expect to learn when getting the result of a random experiment.

There are several properties which you would expect from such a measure:

  • It should only depend on the probabilities, that is, you have a function $H(p_1,\ldots,p_n)$.

  • A minimal change of the probabilities should not drastically change how much you expect to learn. That is, $H$ should be a continuous function of the probabilities.

  • The amount of what you learn should not depend on how you label the results. That is, $H$ should be symmetric in its argument.

  • If you can predict the outcome of an experiment with certainty, then you haven't learned anything when you learn the result. That is, $H(1,0,\ldots,0)=0$.

  • Consider a two-stage experiment where you first do an experiment having $n$ possible outcomes with probabilities $(p_1,\ldots,p_n)$, and then if outcome $n$ is obtained, you do another random experiment with two outcomes, probabilities $q$ and $1-q$. Note that the combined experiment then has probabilities $(p_1,\ldots,p_n q, p_n(1-q))$.

    How much information do you expect to get from learning the complete result? Well, you certainly learn the result of the first stage, $H(p_1,\ldots,p_n)$. Now if the result of the first stage is anything but $n$, that's all you learn, but if result $n$ is obtained, which you get with probability $p_n$, you get the additional information $H(q,1-q)$. Therefore the total expected information from that experiment is $$H(p_1,\ldots,p_n q, p_n(1-q)) = H(p_1,\ldots, p_n) + p_n H(q,1-q)$$ Note that one consequence of this is that $$H(p_1,\ldots,p_n,0) = H(p_1,\ldots,p_n)$$ (just set $q=1$ and use the previously established condition that $H(1,0)=0$). Another easily derivable consequence of this is that for two independent experiments, the entropies simply add up. Which is also something you'd expect from a reasonable measure of expected information gain.

Now it turns out that the above conditions are already sufficient to fix entropy up to a constant factor.

$\endgroup$

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