Independence bound on Entropy

$...................................$

A consequence of the Chain Rule for Entropy is that if we have many

different random variables X$1$;X$2$; :::;Xn$,$ then the sum of all their

individual entropies must be an upper bound on their joint entropy:

H$($X$1$;X$2,,,,$Xn$)<=$ Xn i$=1$ H$($Xi $)$

Their joint entropy achieves this upper bound only if all of these n

random variables are independent.

Another upper bound to note is that for any single random variable X

which has N possible values, its entropy H$($X$)$ is maximised when all

of those values have the same probability pi $=1/$N$.$ In that case,

H$($X$)=$

X

i

pi log$2$ pi $=$ XN $11$N log$21$ N$=$ log$2$ N :

We shall use this fact when evaluating the eciency of coding schemes