0
$\begingroup$

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)$?
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, jkabrg. Is there some intuition to the log(1/k) that appears added? $\endgroup$ – user393650 Nov 27 '16 at 20:35
  • $\begingroup$ @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$ $\endgroup$ – man and laptop Nov 27 '16 at 20:40
  • $\begingroup$ @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$ $\endgroup$ – man and laptop Nov 27 '16 at 20:41
  • $\begingroup$ @user393650 So essentially, $\log \frac1k$ comes from the initial choice of $S_i$. $\endgroup$ – man and laptop Nov 27 '16 at 20:44
  • $\begingroup$ @user393650 I forgot to include the negation. It should be $\log k$ $\endgroup$ – man and laptop Nov 27 '16 at 20:46
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.