Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The entropy (self information) of a discrete random variable X is calculated as:

$$ H(x)=E(-log[P(X)]) $$

What does the -log[P(X)] mean? It seems to be something like ""the self information of each possible outcome of the random variable X".

And why do we use log function to calculate it?

ADD 1

Well, below is my reasoning:

The root motivation is to quantify/measure the uncertainty contained in a random variable.

Intuitively, people tend to agree that there's some connection between uncertainty and probability. And still intuitively, people shall agree that:

  • the more probability an outcome has, the less uncertainty it has.
  • thus, the less probability an outcome has, the more uncertainty it has.

So, I think if we want to measure the uncertainty for an outcome of a random variable, the measure function should satisfy:

  • the value of uncertainty measure should be positive (human instinct when counting)
  • the value of this measure for the uncertainty of an outcome should be monotonic decreasing function of the probability of that outcome.
  • for outcomes of independent experiments, the uncertainty should be additive. That is for P(A)*P(B), the total uncertainty should be the sum of A's and B's. (This is kind of instinctive, too.)

Then I come to the choice of -log[p(i)] as the measure of uncertainty of each possible outcome, or self-information of each outcome.

Then I treat the entropy as the weighted average of the self-information of all possible outcomes.

I just read the book <Information Theory, Inference and Learning Algorithms> by MacKay. The author indeed gives a similar explanation to mine. And he name it the information content of each outcome. It is not difficult to see that entropy better describes a random variable than the information content.

And it is coincidental that the formula we intuitively found to measure the average information content of a random variable has a similar form to the one of entropy in thermodynamics. Thus comes the name information entropy...

BTW I want to quote some words from Einstein...

"It is not so important where one settles down. The best thing is to follow your instincts without too much reflection."

--Einstein to Max Born, March 3, 1920. AEA 8-146

ADD 2

Following my above reasoning, I tried to derive the calculation of entropy for a continuous random variable Y in a similar way. But I was blocked. Details below.

Let Y's p.d.f be: $$f(y)$$

Then, if we strictly follow my previous reasoning, then we should pick up a small interval of I, and the probability of Y within interval I is given by: $$P(y\ within\ I)=\int_If(y)dy$$Then the measure of uncertainty for Y to fall in interval I should be: $$m(y\ within\ I) = -log\int_If(y)dy$$ Then, to get the entropy, we should get the expectation/average of this measure m, which is essentially: $$E[m(y\ within\ I)]$$ and it can be expanded as below:

$$ \int{P(y\ within\ I)*m(y\ within\ I)}dI =\int{(\int_I{f(y)dy}*{(-log\int_If(y)dy)})dI} $$

I found myself stuck here because the interval I is not strictly defined.

Then I find from here the authoritative definition of entropy of continuous random variable:

$$ H(Y)=-\int{f(y)log[f(y)]dy} $$

The p.d.f. $f(y)$ can certainly be $> 1$, so the $H(Y)$ can be negative, while in discrete scenario, the $H(X)$ is always non-negative.

I cannot explain the why this in-consistence is happening. For now, I can only consider it as a philosophical difficulty regarding continuity and discreteness.

Some of my personal feeling (can be safely ignored):

In the discrete scenario, the concrete countable outcome provide the foothold for us to carry out our calculation. But in the continuous scenario, there's no such ready-made foothold (unless we can somehow make one). Without such foothold, it feels like we just keep falling into the endless hollowness of mind.

Anyone could shed some light?

share|improve this question
    
ADD 1 is a very good explanation. –  Martín-Blas Pérez Pinilla Feb 4 at 17:37
add comment

3 Answers 3

Easy illustrative example:

Take a fair coin. $P({\rm each\ result})=1/2$. By independence, $P({\rm each\ result\ in\ n\ tosses})=1/2^n$. The surprise in each coin toss is the same. The surprise in $n$ tosses is $n\times$(surprise in one toss). The $\log$ makes the trick. And the entropy is the mean surprise.

share|improve this answer
    
It's an interesting/intuitive explanation when you mention "the surprise in n tosses is n×(surprise in one toss)" –  smwikipedia Feb 4 at 14:43
add comment

In his 1948 paper Claude Shannon introduced the entropy $H$ of a discrete random variable $X$ with probabilities $p_1, \dots, p_n$ as a function which satisfied three requirements, which should provide a measure of the information contained in $X$:

  1. $H$ should be continuous in the $p_i$.
  2. If all the $p_i$ are equal, $p_i = \frac{1}{n}$, then $H$ should be a monotonic increasing function of $n$. With equally likely events there is more choice, or uncertainty, when there are more possible events.
  3. If a choice be broken down into two successive choices, the original $H$ should be the weighted sum of the individual values of $H$.

He further explains what property 3 means with a nice example. Then, in appendix 2, he shows that only a function of the form $$K \sum_{i=1}^n p_i \log(p_i)$$ can satisfy all these three requirements, where $K$ is some multiplicative constant.

share|improve this answer
    
From the perspective of probability, the entropy is just an expectation of -log[P(i)], so -log[P(i)] must have some solid meaning. So what is it? –  smwikipedia Feb 4 at 14:55
    
Unfortunately, I cannot offer some intuitive explanation to this expectations, and I see that this answer is not fully satisfying. –  Roland Feb 4 at 14:57
    
It does reveal something. Thanks. Actually, since the entropy/self-information is used to quantify/measure the uncertainty of a random variable, I did think about selecting a mathematical function according to a set of preferred properties. These properties are based on some common sense about the relation between uncertainty and information gain. It seems Shannon also took this approach. –  smwikipedia Feb 4 at 15:01
    
There is a more satisfying theorem than Shannon's, due to Faddeev (The notion of entropy of finite probabilistic schemes (Russian), Uspekhi Mat. Nauk 11 (1956), 15-19.) It replaces condition 2 by the weaker and quite natural condition that H is a symmetric function of its arguments. It's interesting that in the proof, to prove $H(1/n,1/n,...,1/n) = -k\log(n)$ for some $k > 0$ he needs to use the infinitude of the primes. –  KCd Feb 5 at 8:58
add comment

Assume that one repeatedly draws values from a finite set $S$ of size $|S|$ according to a distribution $p=(p_x)_{x\in S}$. After one draw, there are $|S|$ possible results, after two draws there are $|S|^2$, and so on, so one can get the impression that after $n$ draws, the resulting distribution is spread out on the Cartesian product $S^n$, whose size is $|S|^n$. And indeed it is, but this view is deceptive because the distribution is extremely unevenly spread out on $S^n$. Actually:

There exists a subset $T_n\subset S^n$, much smaller than $S^n$, on which nearly all the distribution of the sample of size $n$ is concentrated. And in $T_n$, the weight of each element is roughly the same...

In other words, everything happens as if the combined result of the $n$ first draws was chosen uniformly randomly in $T_n$. What connects the dots is that the size of $T_n$ is $\mathrm e^{nH}$ for some deterministic finite number $H$. (Actually, the size of $T_n$ is $\mathrm e^{nH+o(n)}$.) Surely you recognized that $H$ is the entropy of the distribution according to which one is drawing the values from $S$, that is, $$ H=-\sum_{x\in S}p_x\log p_x=-E[\log p_X], $$ where $X$ is any random variable with distribution $p$.

This surprisingly general phenomenon, related to what is called concentration of measure, quantifies $\mathrm e^H$ as the (growth of the) effective size of the sample space. As direct consequences, $0\leqslant H\leqslant\log|S|$, $H=0$ if and only if $p$ is a Dirac measure and $H=\log|S|$ if and only if $p$ is uniform.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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