Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Theorem 7 in Shannon's seminal paper A Mathematical Theory of Communication states:

"The output of a finite state transducer driven by a finite state statistical source is a finite state statistical source, with entropy (per unit time) less than or equal to that of the input. If the transducer is non-singular they are equal."

Basically, it says that a transducer cannot increase the entropy of source. It includes a proof, which I can't make much sense of. I want a justification (even if only by intuition) of how this is true.

Here is the included proof:

Let $\alpha$ represent the state of the source, which produces a sequence of symbols $x_i$; and let $\beta$ be the state of the transducer, which produces, in its output, blocks of symbols $y_j$. The combined system can be represented by the "product state space" of pairs $(\alpha, \beta)$. Two points in the space $(\alpha_1, \beta_1)$ and $(\alpha_2, \beta_2)$, are connected by a line if $\alpha_1$ can produce an $x$ which changes $\beta_1$ to $\beta_2$, and this line is given the probability of that $x$ in this case. The line is labeled with the block of $y_j$ symbols produced by the transducer. The entropy of the output can be calculated as the weighted sum over the states. If we sum first on $\beta$ each resulting term is less than or equal to the corresponding term for $\alpha$, hence the entropy is not increased. If the transducer is non-singular, let its output be connected to the inverse transducer. If $H'_1$, $H'_2$ and $H'_3$ are the output entropies of the source, the first and second transducers respectively, then $H'_1 \geq H'_2 \geq H'_3 = H'_1$ and therefore $H'_1 = H'_2$.

share|improve this question
    
I edited the question based on the paper. The complete paper can be found here: cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf. –  Srivatsan Nov 14 '11 at 0:56
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.