Entropy of Multiple Information Sources

260 Views Asked by At

Assume you have $k$ information sources $S_1 \ldots S_k$. Each one can transmit $n$ symbols, and all the symbols are different between sources.

Let $S$ be a new source capable of transmiting $nk$ symbols. It does so by randomly choosing, in an uniform way, $S_i \in {S_1 \ldots S_k}$ to do the transmission.

  • What's the value of the entropy of $S$, $H(S)$?
2

There are 2 best solutions below

6
On

If $S$ transmits the $j$th symbol by $S_i$, we say that $S=(i,j)$ and $S_i = j$. $H(S)$ expands to $$-\sum_{i=1}^k \sum_{j=1}^n \Pr[S=(i,j)]\log \Pr[S=(i,j)]$$ This expands to $$-\sum_{i=1}^k \sum_{j=1}^n \frac1k\Pr[S_i=j]\log \left( \frac1k\Pr[S_i=j]\right)$$ which equals $$\begin{align}&-\sum_{i=1}^k \sum_{j=1}^n \frac1k\Pr[S_i=j]\log\frac1k - \sum_{i=1}^k \sum_{j=1}^n \frac1k\Pr[S_i=j]\log \left( \Pr[S_i=j)]\right)\\&=\log k - \frac1k \sum_{i=1}^k \sum_{j=1}^n \Pr[S_i=j]\log \left( \Pr[S_i=j)]\right)\\&=\log k+\frac1k\sum_{i=1}^k H(S_i) \end{align}$$

[edit]

Initially I wrote the final expression as $\log \frac 1k+\frac1k\sum_{i=1}^k H(S_i)$. That's because I forgot to add the minus sign to the expression of the entropy.

1
On

Let $Z$ be a random variable, its value corresponds to the index of the selected source. If $X$ is the emitted symbol, then, by the chain rule:

$$ H(X,Z)=H(X\mid Z) + H(Z)=H(Z \mid X) + H(X) \tag{1}$$

But $H(Z \mid X)=0$, because knowing the emitted symbol implies knowing the selected source (this is where the assumption that all sources emit different symbols is crucial). Then

$$H(X)= H(X \mid Z ) + H(Z)$$

But, from the definition of conditional entropy

$$ H(X \mid Z )=\sum_{z=1}^k p(Z=z) \, H(X\mid Z=z)=\sum_{z=1}^k p_z H_z$$

and the entropy is then the weighted average of the individual entropies plus the entropy of the "mixing" distribution.

$$H(X)= \sum_{z=1}^k p_z H_z + H({\bf p_z})$$

In our particular case in which the sources are equiprobable, $p_z=\frac 1k$, this gives

$$H(X)= \frac{1}{k} \sum_{z=1}^k H_z + \log_2(k)$$