Does anybody know a book where the proof of recursivity property of Shannon's Entropy can be found?
I mean this: $$H(q_1,...,q_n)=H(q_1 + q_2, q_3,...,q_n) + (q_1 +q_2)H( \frac{q_1}{q_1+q_2} , \frac{q_2}{q_1+q_2} )$$
Where $q_i$ is probability of i-th value.
On
Intuitively for proof I drew a pie chart, with probabilities $p_1$, $p_2$, and $p_*$ for all other probabilities.
Then the Entropy formula is something like: what is the expected number of bits would I need to describe picking a random piece of the pie with given probabilities.
That event can also be described as an event of picking either the piece with probability $p_*$ or the piece with probability $p_1 + p_2$ . However, you then still need the Entropy formula for some extra bits to describe the selection between $p_1$ and $p_2$.
Since it is an expected number, we have to take into account probability $p_1 + p_2$, and the Entropy formula for selecting between only $p_1$ and $p_2$ (normalized).
$H(p_1, p_2, p_*) = H(p_1 + p_2, p_*) + (p_1 + p_2) * H(p_1/(p_1+p_2), p_2/(p_1+p_2))$.
I hope this intuitive proof is sufficient, because this was 20 years ago for me, and the formal proof/calculation would require too much from me after all that time.
Actually, I tried it on paper, and you only have to expand
$$(p_1 +p_2)H( \frac{p_1}{p_1+p_2} , \frac{p_2}{p_1+p_2})$$ With the formula $H(p) = -p *ln(p)$, and $ln(a/b) = ln(a) - ln(b)$, it is provable that it equals $$H(p_1) + H(p_2) - H(p_1 + p_2)$$
Use the definition. We have $$H(p_1,p_2,\ldots,p_n) = -\sum_{k=1}^np_k\log p_k$$
and
$$H(p_1+p_2,\ldots,p_n) = -(p_1+p_2)\log(p_1+p_2) - \sum_{k=3}^np_k\log p_k$$
so
$$H(p_1,p_2,\ldots,p_n) - H(p_1+p_2,\ldots,p_n) = -p_1\log p_1 - p_2\log p_2 + (p_1+p_2)\log (p_1+p_2)$$
and the right hand side can be written (after a bit of algebra):
$$-(p_1+p_2)\left( \frac{p_1}{p_1+p_2}\log \left[\frac{p_1}{p_1+p_2}\right] + \frac{p_2}{p_1+p_2}\log\left[\frac{p_2}{p_1+p_2}\right]\right)$$
which is nothing but $(p_1+p_2)H\left(\frac{p_1}{p_1+p_2},\frac{p_2}{p_1+p_2}\right)$.