The Gold Standard of Information Theory

A weather station sends one of three status symbols. The receiver needs to recover the symbol correctly, while the designer wants to use the connection efficiently. Information theory gives a mathematical language for that problem: what alternatives can occur, how likely are they, and what can be communicated through the available channel?

A source produces symbols or messages under a model. An encoder represents them for storage or transmission. A channel carries that representation, potentially introducing changes. A decoder attempts to recover the intended message. These roles can be physical devices or mathematical abstractions.

The gold standard of information theory is a precise account of uncertainty, representation and communication limits, with the model and units kept visible. A calculation becomes useful when a reader can tell which question it answers and which assumptions support it.

Begin a study problem by writing the alphabet of possible symbols, the probability model, the coding rule and the receiver’s task. That small description prevents several different meanings of information from being mixed together.

For an outcome with probability p greater than zero, its self-information or surprisal is −log₂(p) bits. Under this definition, an outcome assigned a smaller probability carries a larger surprisal when it occurs.

An outcome with probability one has zero surprisal: the model already predicts it with certainty. An outcome with probability one-half has one bit; an outcome with probability one-quarter has two bits. These are logarithmic quantities, rather than counts of letters in a message.

The probability belongs to a model. An unusual observation under a poor model may tell us that the model needs revision. Do not turn a calculated surprisal into a claim that the event is objectively remarkable to every observer.

Define the event carefully. The probability of a particular symbol, a complete sequence and a category of sequences can differ greatly. A calculation using one event cannot silently become an answer about another.

For a discrete random variable X with possible outcomes x, Shannon entropy is H(X) = −Σ p(x) log₂ p(x), measured in bits when the logarithm has base two. A zero-probability outcome contributes zero by the usual limiting convention.

Entropy averages surprisal across the possible outcomes. It describes the distribution before the particular outcome is known. The surprisal of one observed symbol and the entropy of its source are related quantities with different roles.

Consider a fictional source emitting A, B and C with probabilities one-half, one-quarter and one-quarter. Their surprisals are one, two and two bits. The average is (0.5 × 1) + (0.25 × 2) + (0.25 × 2) = 1.5 bits per symbol.

A fractional average is entirely possible even though the codeword for a particular symbol contains a whole number of binary digits. Averaging over symbols and coding individual symbols are different operations. Keep ‘per symbol’ attached to the 1.5-bit result.

For independent repeated draws from this stated distribution, joint entropy grows by 1.5 bits per draw. If successive symbols depend on earlier ones, that multiplication needs reconsideration: the single-symbol frequencies do not describe every sequence relationship.

Use the same fictional source. Assign A the codeword 0, B the codeword 10 and C the codeword 11. No complete codeword is the beginning of another complete codeword. This prefix property lets the receiver recognise a codeword as soon as its final bit arrives.

The sequence A, C, B becomes 0 followed by 11 followed by 10, giving 01110. Reading from the beginning with the shared codebook recovers A, then C, then B. The receiver also needs an agreed message boundary or length convention.

The expected code length is (0.5 × 1) + (0.25 × 2) + (0.25 × 2) = 1.5 bits per source symbol. A fixed two-bit representation for each of the three symbols would use two bits per symbol, so the expected payload saving is 0.5 bits per symbol, or 25% of that two-bit baseline.

This comparison excludes headers, codebook transmission, padding and other implementation costs. A short file can grow once those costs are included. A mathematical payload calculation should retain its boundary when it is discussed as a practical storage claim.

The table connects each probability to both its surprisal and its assigned code length. The equality is a feature of this deliberately convenient example; arbitrary distributions do not automatically admit a one-symbol binary prefix code with average length exactly equal to entropy.

Lossless compression preserves enough information to recover the original data exactly under the agreed format. It takes advantage of structure the encoder and decoder can represent efficiently. Source probabilities, repeated patterns and context can provide different kinds of structure.

A useful introductory bound is that the expected length L of a binary prefix code for one discrete symbol is at least H(X), with a suitable code achieving L less than H(X) + 1. The comparison concerns expected length under the stated source distribution, not a promise about every individual file.

Coding blocks can reduce the overhead per source symbol under suitable source assumptions. Real compressors must also represent models, delimit data and operate within memory and time constraints. An entropy calculation identifies a theoretical reference point; it does not by itself select a practical file format.

Lossy compression answers another question: what representation can meet a specified distortion or task criterion while using fewer bits? A smaller output alone does not establish acceptable quality. State what can change and how that change will be assessed.

An encoder that claims to shorten every possible input while preserving exact recovery raises a counting problem. There are fewer binary strings shorter than a given length than strings at that length. A uniquely reversible system cannot assign all inputs distinct shorter outputs without some other information carrying the missing distinction.

A channel model describes the relationship between transmitted input and received output. A simple model may assume that each bit independently flips with a fixed probability. A real connection may instead have bursts, interruptions, changing conditions or dependencies between errors.

Channel capacity concerns the greatest rate at which information can be conveyed with arbitrarily small decoding error under the model’s conditions and appropriate coding limits. For a discrete channel, bits per channel use is a common unit. Converting that to bits per second requires a rate of channel use.

Capacity, raw signalling rate and delivered application throughput are different measurements. Headers, retransmissions, access competition, delay requirements and implementation choices can affect the amount of useful application data delivered.

Claude Shannon’s A Mathematical Theory of Communication established foundational connections between statistical source structure, coding and communication limits. Use the result with its mathematical conditions, including the distinction between limits approached by suitable codes and guarantees for a particular short message.

Suppose a fictional binary channel flips each transmitted bit independently with probability 0.1. Send one source bit three times: zero becomes 000 and one becomes 111. The receiver chooses the majority of the three received bits.

Majority decoding fails when exactly two bits flip or when all three flip. The probability is 3 × (0.1)² × 0.9 + (0.1)³ = 0.027 + 0.001 = 0.028. Under this model, the decoded bit error probability falls from 10% for a single uncoded use to 2.8% for this three-use scheme.

The cost is three channel uses for each source bit, giving a code rate of one-third source bit per channel use. The example demonstrates a reliability and resource trade-off. It does not establish that repetition is an efficient way to approach channel capacity.

Independence matters. A disturbance that corrupts all three repetitions together can behave differently from three independent flips. Write down the error mechanism before reusing the calculation for another channel.

Compression can remove representational redundancy, while channel coding can deliberately add structured redundancy for recovery. A complete communication design can use both stages because they serve different purposes.

A receiver may already know something related to the source. Conditional entropy H(X|Y) measures the average uncertainty remaining about X when Y is known. For discrete variables, mutual information I(X;Y) = H(X) − H(X|Y) expresses the corresponding average reduction in uncertainty.

If Y reveals X exactly, the remaining conditional entropy is zero. If X and Y are independent, knowing Y does not change the distribution of X, and their mutual information is zero. These statements concern the specified joint distribution.

A context model for text may assign different probabilities to the next symbol depending on preceding symbols. That can affect compressibility without proving that the model understands the text’s meaning. Predictive relationships and human interpretation need their own evidence.

Mutual information does not establish causation. A statistical relationship can arise through a common cause or other structure. Nor does a high entropy value establish truth, usefulness, importance or cryptographic security.

For an empirical analysis, report what was sampled, how symbols were defined, which dependencies were modelled and how uncertainty in the estimates was handled. A frequency table from a finite sample is evidence about a source, rather than perfect access to its underlying distribution.

A fictional source emits D with probability one-half, E with probability one-quarter and F with probability one-quarter. A proposed binary code assigns D = 1, E = 00 and F = 01. Check the prefix property, calculate expected length and decode 10001.

Then assess this claim: ‘Because the average length is 1.5 bits per symbol, every three-symbol message uses 4.5 bits.’ Explain the confusion and give the actual payload length of the decoded message.

The code is a prefix code: 1 is not the beginning of 00 or 01, and the two two-bit words differ. The expected length is (0.5 × 1) + (0.25 × 2) + (0.25 × 2) = 1.5 bits per symbol.

The bit string 10001 separates as 1 | 00 | 01 and decodes to D, E, F. Its actual payload length is five bits. The average of 1.5 describes an expectation under the source model, so three draws have expected length 4.5 bits; a realised message still has an integer number of bits.

Finally, write one sentence the calculation supports and one it cannot support. It supports a claim about expected payload length under this distribution. It cannot establish whether a particular file format saves space after overhead, or whether the source messages are meaningful or accurate.

Follow the question that remains after the calculations. The guides below connect this root to the existing mathematics, compression, communication and security branches.

Probability and evidence

• Probability: clarify events, distributions and independence.
• Statistics: connect models with sampled evidence.
• Discrete Mathematics: examine finite structures and counting.

Compression methods and limits

• Entropy Coding: follow the connection between probabilities and code lengths.
• Arithmetic Coding: explore coding across a message.
• LZ77, LZ78 and LZW: investigate dictionaries and repeated patterns.
• The Impossible Box: continue into the limits of universal size reduction.

Reliable communication and security

• Error-Correcting Codes, Parity and Reliable Data Transfer: connect redundancy with transmission checks.
• Telecommunications and Wireless Communication: place channel models in service and engineering contexts.
• Cryptography: examine security goals and adversarial assumptions.

Sources and a useful next step

Shannon’s paper and MIT’s information theory lecture notes provide the mathematical foundations. MIT’s chapters on entropy and lossless compression offer deeper treatment of the definitions and coding bounds.

For your next exercise, describe a source, build a small code and distinguish its expected length from one realised message. Then explain how a noisy channel changes the receiver’s task. This is the learning transfer developed in The Gold Standard of Education.