# Entropy of Multiple Information Sources

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)$?

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}

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.

• Thank you, jkabrg. Is there some intuition to the log(1/k) that appears added? – user393650 Nov 27 '16 at 20:35
• @user393650 If you think of the situation when each $S_i$ can only output one symbol, then the result agrees with the fact that the entropy should be $\log \frac1k$ – man and laptop Nov 27 '16 at 20:40
• @user393650 Also, if each $S_i$ has the same distribution then the result agrees with the fact that $H((A,B)) = H(A) + H(B)$ if $A$ and $B$ are independent. In our case, $A$ would be $\{1, \dots, k\}$ and $B$ would be $S_i$ – man and laptop Nov 27 '16 at 20:41
• @user393650 So essentially, $\log \frac1k$ comes from the initial choice of $S_i$. – man and laptop Nov 27 '16 at 20:44
• @user393650 I forgot to include the negation. It should be $\log k$ – man and laptop Nov 27 '16 at 20:46

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)$$