# Pattern Recognition and Machine Learning (Bishop) - Exercise 1.28

1.28 In Section 1.6, we introduced the idea of entropy $h(x)$ as the information gained on observing the value of a random variable $x$ having distribution $p(x)$. We saw that, for independent variables $x$ and $y$ for which $p(x,y) = p(x) p(y)$, the entropy functions are additive, so that $h(x,y) = h(x) + h(y)$. In this exercise, we derive the relation between $h$ and $p$ in the form of a function $h(p)$. First show that $h(p^2) = 2 h(p)$, and hence by induction that $h(p^n) = n h(p)$ where $n$ is a positive integer. Hence show that $h(p^{n/m}) = (n/m) h(p)$ where $m$ is also a positive integer. This implies that $h(p^x) = x h(p)$ where $x$ is a positive rational number, and hence by continuity when it is a positive real number. Finally, show that this implies $h(p)$ must take the form $h(p) \propto \ln p$.

(Original image here.)

I am having a few problems with this exercise, I will try to list them and perhaps you can help on some of them:

1. Essentially, I don't understand what kind of function is $h$, because the first two lines of the problem definition make me think that its input is a random variable $x$ and its ouput a real number $h(x)$. But next, the problem uses the notation $h(x,y)$, implying that now $h$ is a function of 2 random variables $x$ and $y$, yielding a real number $h(x,y)$ as output. So what would be the correct or formal way to define $h$?
2. In connection with the first item, now in the 5th line it reads $h(p)$... so if switching between 1 and 2 random variables as inputs wasn't enough, now the input is a probability density? $h$ must be a very robust function for sure... ok I guess that so far the question is the same as in item 1, i.e., what is $h$?
3. The first step of the problem definition is to show $h(p^2) = 2 \, h(p)$ - ignoring the issues I described previously - I can't see how this is achieved by using those two hypothesis about independent variables. A have a feeling that the idea is to do something like (warning: the following is nonsense): $h(p^2) = h(p,p) = h(p) + h(p) = 2\, h(p)$ the first equality being wrong because I magically split the $p^2$ into two input variables, the second one being also wrong because I apply a hypothesis given for independent random variables on probability densities of dependent random variables and the last one is ok (!!!). So, what would be a nicer way to fulfill this first step?
4. Finally, is it really the logarithm's family the only solutions that match these requirements? I wonder, for example, what would happen if the argument function was used (like arg$(z)$ in complex analysis) since it satisfies the same properties as the logarithm regarding the product and power of its inputs.

Help in any of these items will be appreciated!

In case you are interested, there are many online sources of the book, e.g. here, the topic is covered in page 48 of the book (68 of the pdf) and the problem definition - picture uploaded - is in page 64 of the book (84 of the pdf).

EDIT: I've found this article on Wikipedia, in which my first two items are answered, via a more clear notation for the functions and variables involved in the problem. Still looking for 3 and 4...

• Bishops move diagonally. I know what entropy is but I have no idea what that question means. $H(X)$ is defined as the entropy of a random variable $X$, I am a bit concerned about using smallcase $h(x)$, and am very concerned about using $h(p)$ in the very next sentence since $x$ and $p$ seem very different objects. And if $p$ somehow represents a mass function then $p^2$ does not. Are you able to toss the book into the sea? – Michael Aug 21 '18 at 4:37
• The sentence "a random variable $x$ having distribution $p(x)$" says to me: "The notation in this book will not make any sense, since the author does not know the difference between a random variable, an event, and a parameter (free variable)." – Michael Aug 21 '18 at 4:43
• In that order: thanks for the tip about bishops, so far I was using them to dig inside my nose and ears. About "h" and "H": I think that is also a mistake, and he refers to information $h(x)$ instead of entropy $H(x)$. Finally, I am from Buenos Aires, being at least 300 km away from the sea... I am a few km away from the river though – Javi Aug 21 '18 at 4:45

After some hours of research I've found a few sites which altogether answer these questions.

Regarding items 1 and 2, it looks like there is indeed a severe abuse of notation every time the author refers to function $h$. This function seems to be the so-called self-information and it is usually defined over probability events or random variables as well. I find this article very clarifying in this respect.

Regarding item 4, for what I have seen, it seems that under certain conditions that the self information functions must satisfy, the logarithm if the only possible choice. The selected answer in this post was particularly useful, and also the comments on the question. This topic is also discussed here, but I prefer the previous link.

Finally, I have not found an answer for item 3. Actually, I really think that this step is wrongly formulated due to the imprecision in the definition of function $h$. Nevertheless, the links I have provided as an answer to item 4 lead to the desired result.

• A minor comment to further emphasize that domains are important: The only function $g:[0,1]\rightarrow\mathbb{R}$ that satisfies $g(xy)=g(x)+g(y)$ for all $x, y \in [0,1]$ is the always-zero function $g(x)=0$ for all $x \in [0,1]$, since for all $y \in [0,1]$ we have $$g(0)=g(0y)=g(0)+g(y) \implies g(y)=0$$ I observe the answer in your linked post is careful to consider $g:(0,1]\rightarrow\mathbb{R}$. – Michael Aug 26 '18 at 3:30

We can write $$h(x) = F(p(x))$$ because $$h(x)$$ is a function of $$p(x)$$. Note that $$h(x,y) = F(p(x,y))$$.

$$h(x,x) = F(p(x,x))=F(p(x) * p(x))=F(p^2)$$ and $$h(x,x) = h(x) + h(x) = F(p(x)) + F(p(x)) = 2*F(p(x))$$.

Hence, we get $$F(p^2) = 2*F(p(x))$$.