Computer Science › Intelligence + Theory
Before any entropy math: a simple pigeonhole counting argument proves no algorithm can losslessly compress every possible input, and in fact the overwhelming majority of inputs of a given length cannot be compressed at all — the ceiling this whole discipline explores is a hard mathematical limit, not a matter of finding a cleverer algorithm.
Defines Shannon's self-information I(x) = −log₂p(x), the log-based measure of how surprising a single outcome is, and derives why the logarithm — additive across independent events, and matching the intuition that rarer outcomes carry more information — is the only measure with the properties Shannon required, not an arbitrary choice.
Entropy H(X) = ∑ₓ p(x)·I(x) is exactly the expected self-information of a random variable — computed here by hand for several small alphabets — and is proved to be maximized by the uniform distribution and bounded between 0 and log₂(n), making it the single number that captures how uncertain, and therefore how compressible, a source really is.
KL divergence D(p‖q) is derived as the expected number of extra bits paid for encoding data from p with a code built for q instead — worked through concretely with two differently-biased coins — and its non-negativity (Gibbs' inequality) is proved via Jensen's inequality; cross-entropy H(p,q) = H(p) + D(p‖q) is then identified as exactly the loss `deep-learning`'s `softmax-and-cross-entropy-loss` derived independently and self-contained, closing the loop that concept deliberately left open.
Extends entropy to pairs of random variables: joint entropy H(X,Y) measures the uncertainty of the pair together, conditional entropy H(Y|X) measures what's left once X is known, and the chain rule H(X,Y) = H(X) + H(Y|X) ties the two together — proved in general and checked by hand against a real joint distribution.
Mutual information I(X;Y) = D(p(x,y) ‖ p(x)p(y)) is defined as the KL divergence between the true joint distribution and the product of the marginals — equivalently H(X) − H(X|Y) — quantifying exactly how many bits knowing Y saves when describing X, and proved equal to zero precisely when X and Y are independent.
Shannon's source coding theorem — no lossless code can beat an average length of H(X) bits per symbol, and entropy is asymptotically achievable by some code — is stated and motivated with a real proof sketch, in the same counting-argument spirit already used for `algorithms`'s comparison-sort lower bound.
Kraft's inequality ∑ᵢ 2^(−lᵢ) ≤ 1 characterizes exactly which sets of codeword lengths admit a prefix-free code, proved directly from the one-to-one correspondence between a prefix-free code and a binary tree with symbols at the leaves — the same tree structure already covered in `trees` and `binary-trees-terminology-and-representation`, now put to a genuinely new use.
The Huffman coding algorithm — repeatedly merge the two least-probable symbols into a new combined node — is built and traced by hand into a complete binary tree for a small real alphabet with real frequencies, producing a concrete prefix-free code and its exact average codeword length.
Huffman coding is proved optimal among all prefix-free codes via an exchange argument built on the same template `algorithms` already established for activity selection — showing the two least-probable symbols can always be placed as siblings at maximum depth in some optimal code tree without any loss in expected length.
A survey of what real systems use after Huffman: arithmetic coding removes Huffman's integer-bits-per-symbol restriction to get arbitrarily close to the entropy limit, and LZ77-style dictionary compression — combined with Huffman coding itself inside DEFLATE, the algorithm behind gzip and PNG — exploits repeated substrings that a single fixed symbol-frequency table can never capture.
The binary symmetric channel — each transmitted bit independently flipped with probability p, a genuine Bernoulli trial applied per bit — is introduced as the canonical toy noisy channel that makes every capacity and coding-theorem argument in this cluster concrete and computable by hand.
Channel capacity C = maxₚ₍ₓ₎ I(X;Y), the largest mutual information achievable over all possible input distributions, is defined and computed by hand for the binary symmetric channel, yielding the exact closed form C = 1 − H(p) and confirming that a noisier channel (larger crossover probability) has strictly lower capacity.
Shannon's noisy-channel coding theorem — reliable communication at any rate below capacity is possible, and impossible above it — is stated with its real-world implication made concrete, with the achievability direction motivated at the intuition level of typical sequences and random coding appropriate for a CS audience, rather than the full graduate-level proof machinery.
Connects the abstract capacity and coding-theorem machinery to real error-correcting codes — parity bits and Hamming codes worked by hand — developing the forward-error-correction technique that `computer-networks`'s link-layer concept explicitly named but declined to develop, closing that discipline's deferred thread.
A capstone tracing one small real message end-to-end: computing its source entropy by hand, building its Huffman code and measuring the real compression ratio achieved against the theoretical entropy limit, then pushing the compressed bits through a binary symmetric channel and checking the message's transmission rate against the channel's real capacity.
Part of the Computer Science curriculum.
Before any entropy math: a simple pigeonhole counting argument proves no algorithm can losslessly compress every possible input, and in fact the overwhelming majority of inputs of a given length cannot be compressed at all — the ceiling this whole discipline explores is a hard mathematical limit, not a matter of finding a cleverer algorithm.
Defines Shannon's self-information I(x) = −log₂p(x), the log-based measure of how surprising a single outcome is, and derives why the logarithm — additive across independent events, and matching the intuition that rarer outcomes carry more information — is the only measure with the properties Shannon required, not an arbitrary choice.
Entropy H(X) = ∑ₓ p(x)·I(x) is exactly the expected self-information of a random variable — computed here by hand for several small alphabets — and is proved to be maximized by the uniform distribution and bounded between 0 and log₂(n), making it the single number that captures how uncertain, and therefore how compressible, a source really is.
KL divergence D(p‖q) is derived as the expected number of extra bits paid for encoding data from p with a code built for q instead — worked through concretely with two differently-biased coins — and its non-negativity (Gibbs' inequality) is proved via Jensen's inequality; cross-entropy H(p,q) = H(p) + D(p‖q) is then identified as exactly the loss `deep-learning`'s `softmax-and-cross-entropy-loss` derived independently and self-contained, closing the loop that concept deliberately left open.
Extends entropy to pairs of random variables: joint entropy H(X,Y) measures the uncertainty of the pair together, conditional entropy H(Y|X) measures what's left once X is known, and the chain rule H(X,Y) = H(X) + H(Y|X) ties the two together — proved in general and checked by hand against a real joint distribution.
Mutual information I(X;Y) = D(p(x,y) ‖ p(x)p(y)) is defined as the KL divergence between the true joint distribution and the product of the marginals — equivalently H(X) − H(X|Y) — quantifying exactly how many bits knowing Y saves when describing X, and proved equal to zero precisely when X and Y are independent.
Shannon's source coding theorem — no lossless code can beat an average length of H(X) bits per symbol, and entropy is asymptotically achievable by some code — is stated and motivated with a real proof sketch, in the same counting-argument spirit already used for `algorithms`'s comparison-sort lower bound.
Kraft's inequality ∑ᵢ 2^(−lᵢ) ≤ 1 characterizes exactly which sets of codeword lengths admit a prefix-free code, proved directly from the one-to-one correspondence between a prefix-free code and a binary tree with symbols at the leaves — the same tree structure already covered in `trees` and `binary-trees-terminology-and-representation`, now put to a genuinely new use.
The Huffman coding algorithm — repeatedly merge the two least-probable symbols into a new combined node — is built and traced by hand into a complete binary tree for a small real alphabet with real frequencies, producing a concrete prefix-free code and its exact average codeword length.
Huffman coding is proved optimal among all prefix-free codes via an exchange argument built on the same template `algorithms` already established for activity selection — showing the two least-probable symbols can always be placed as siblings at maximum depth in some optimal code tree without any loss in expected length.
A survey of what real systems use after Huffman: arithmetic coding removes Huffman's integer-bits-per-symbol restriction to get arbitrarily close to the entropy limit, and LZ77-style dictionary compression — combined with Huffman coding itself inside DEFLATE, the algorithm behind gzip and PNG — exploits repeated substrings that a single fixed symbol-frequency table can never capture.
The binary symmetric channel — each transmitted bit independently flipped with probability p, a genuine Bernoulli trial applied per bit — is introduced as the canonical toy noisy channel that makes every capacity and coding-theorem argument in this cluster concrete and computable by hand.
Channel capacity C = maxₚ₍ₓ₎ I(X;Y), the largest mutual information achievable over all possible input distributions, is defined and computed by hand for the binary symmetric channel, yielding the exact closed form C = 1 − H(p) and confirming that a noisier channel (larger crossover probability) has strictly lower capacity.
Shannon's noisy-channel coding theorem — reliable communication at any rate below capacity is possible, and impossible above it — is stated with its real-world implication made concrete, with the achievability direction motivated at the intuition level of typical sequences and random coding appropriate for a CS audience, rather than the full graduate-level proof machinery.
Connects the abstract capacity and coding-theorem machinery to real error-correcting codes — parity bits and Hamming codes worked by hand — developing the forward-error-correction technique that `computer-networks`'s link-layer concept explicitly named but declined to develop, closing that discipline's deferred thread.
A capstone tracing one small real message end-to-end: computing its source entropy by hand, building its Huffman code and measuring the real compression ratio achieved against the theoretical entropy limit, then pushing the compressed bits through a binary symmetric channel and checking the message's transmission rate against the channel's real capacity.