For a fixed estimated probability mass function , the estimated joint probability mass function is . If whenever , the strong law of large numbers gives the mismatched asymptotic equipartition property:
Here is cross-entropy, and the last equality is cross-entropy equals entropy plus relative entropy. The Kullback-Leibler divergence measures the extra average logarithmic loss from the estimated law.
If for some with , let . The probability that none of the first observations belongs to this set is . Almost surely such a symbol eventually occurs, after which forever. Thus the limit is , consistent with infinite cross-entropy and infinite Kullback-Leibler divergence.
The independent and identically distributed hypothesis factors the joint probability mass function:
Symbols outside the support of a probability distribution never occur, almost surely. On its finite positive probability support, is bounded, so the strong law of large numbers applies:
This is the asymptotic equipartition property with the sign appropriate to a logarithm of a probability mass.
Set , and . If , the two probability mass functions agree and the bound is zero. Otherwise every . The half-interval entropy summand bound, with and , gives
By the triangle inequality, followed by Jensen's inequality for the concave function ,
This proves the requested finite-alphabet entropy continuity bound:
For the entropy summand , differentiation on gives
Since as , its continuous extension to is a concave function.
Fix and define the increment on . In its interior,
Thus the increment is decreasing, and its endpoint values are and . Therefore
The cases follow directly from the endpoint values.
To obtain the sharper half-interval bound, put . It has , while
Hence is a concave function on and lies above the chord joining its zero endpoints. Thus there, proving
Let and let be the error indicator random variable. Because is determined by , the chain rule for conditional entropy in its two orders gives
By conditioning reduces entropy, . On , knowing determines , so the corresponding conditional entropy is zero. On , at most symbols remain possible for . The maximum Shannon entropy of a probability distribution on at most symbols is . Consequently
For an arbitrary function , repeat the argument with . This is still determined by ; when it is zero, , and when it is one, has at most possibilities for each . Thus Fano's inequality gives
Events of zero probability contribute zero to the conditional average, covering the error probabilities zero and one. If , the left side and error probabilities are zero; the trivial conclusion is handled separately instead of writing as an ordinary finite product.
The inequality is true for ordinary addition, and also for addition in a group. For any fixed , the translation is injective, so it merely relabels the probability masses in the conditional distribution. Since are independent random variables,
Averaging over and using conditioning reduces entropy proves entropy monotonicity under independent addition:
There is no requirement that remain in the original finite alphabet. The proof also gives by symmetry. Independence matters: for a nonconstant and , the sum is constant while .
There are two possible messages and three channel uses, giving
Conditional on either transmitted message, a decoding error occurs exactly when at least two of the three bits are flipped. The discrete memoryless channel makes these flips independent, each with probability . Their count therefore has a binomial distribution with parameters . Majority-vote decoding of a repetition code gives
Interchanging the two bit values leaves the binary symmetric channel and majority decision unchanged, so as well. Both the maximum conditional error and the average error, for any message prior, are therefore . The probability of correct decoding for each message is . These are finite-block error probabilities; a channel-capacity statement alone would not determine them.
For every input probability mass function, conditional entropy is nonnegative, so
Taking the maximum over input laws proves bit per channel use. This bound comes from the binary input alphabet itself; no specific transition probabilities or decoder are needed.
Write . Because is determined by , the chain rule for mutual information gives
This is the data processing inequality. It holds for every input probability distribution. Maximizing each side over that same set of input probability distributions gives ; processing cannot increase channel capacity.
A simple sufficient condition for equality is that be injective on the reachable output alphabet. Then can be recovered from , giving and hence for every input law. The input that achieves the original channel capacity therefore achieves it after processing as well. Values of outside reachable outputs are irrelevant.
Injectivity is sufficient rather than necessary. More precisely, for finite alphabets equality in capacity data processing holds exactly when there is an original capacity-achieving input law for which and have conditional independence given . Sufficiency follows from the displayed gap identity. For necessity, maximize at an input law ; if its maximum equals , then , so both inequalities are equalities. Processing may discard output details unrelated to the input without losing channel capacity.
For a discrete memoryless channel with transition probabilities , the conditional probability of a length- output given a length- input factors as
The same transition probabilities apply at each use. Its channel capacity is
The unit is bits per channel use. For finite alphabets the maximum exists by continuity on the probability simplex; with more general alphabets one uses a supremum when appropriate.
An channel code consists of an encoder and a decoder . It represents each of messages by input symbols and recovers a message from the observed output symbols. Its code rate is bits per use. For each message , its conditional error probability is ; an average error also specifies the message probability distribution, while the maximum error takes the largest conditional error.
For an even integer , merge the two least weights once, then repeatedly merge three least weights until only the tree root remains. The initial binary merge leaves an odd number of weighted objects, so the preceding algorithm applies. The initial merged tree parent has two tree children; subsequent tree parents have three. Equivalently, add one zero-weight dummy symbol, run the odd-leaf ternary Huffman coding algorithm, and remove its codeword afterwards. The dummy contributes nothing to expected codeword length.
Here the first merge joins the two weights , producing . The three remaining weights are , and merge directly into the tree root. Assigning the first two tree root branches to the original symbols of weights and gives
The merge-weight check gives as well. For , the first merge is already the tree root; for , outside this case with an even number of symbols, the usual temporary reduced-problem convention would permit an empty word.
For an odd integer , ternary Huffman coding repeatedly merges three smallest weights.
Start with one tree leaf for each source symbol, weighted by its probability. While more than one weighted object remains, choose the three objects with least weights, create their common tree parent with weight equal to their sum, and replace the three by that tree parent. Newly created tree parents participate in subsequent choices. Each merge reduces the number of objects by two; an odd number of objects therefore reaches three and then one, never an unmergeable pair. The final object is the tree root of the code tree.
Label the three outgoing edges at each internal vertex by in any order. The digits along the root-to-leaf graph path give each symbol's codeword. Tree leaves cannot be ancestors of other tree leaves, so this is a prefix code. Ties can be resolved arbitrarily. The expected codeword length is measured in trits, and equals the sum of all merge weights, because each merge adds one digit to every codeword below it.
The structural reason for merging three is that the positive-weight, odd-leaf case has a full ternary tree. Its deepest sibling codeword triple can receive the three least weights by exchanging tree leaf labels, and contracting that triple reduces the problem by two symbols. This explains the recursive construction; a separate optimality proof is not required here.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact