Information theory

Information theory is a branch of mathematics concerned with quantifying information, uncertainty, and the limits of communication. Using probability to model messages and transmission systems, it determines how compactly data can be represented and how reliably it can be transmitted through noise. Its central quantities include entropy, mutual information, and channel capacity. Information here concerns statistical distinguishability and uncertainty, rather than a message’s meaning, truth, or usefulness. (people.math.harvard.edu)

Origins and framework

Claude Shannon established the field’s central framework in his 1948 paper A Mathematical Theory of Communication, published in the Bell System Technical Journal. Building on earlier work by Harry Nyquist and Ralph Hartley, Shannon combined statistical models of information sources with mathematical descriptions of noisy channels. His results connected the uncertainty of messages to the resources required for their transmission. (people.math.harvard.edu)

The basic communication model consists of a source, an encoder, a channel, a decoder, and a destination. The encoder converts a message into a transmissible representation; the channel may introduce noise; the decoder reconstructs the message from the received signal. Sources can produce independent symbols or dependent sequences represented by a stochastic process. Separating statistical structure from semantic content allows the same mathematical framework to describe text, images, and physical signals. (people.math.harvard.edu)

Entropy and uncertainty

For an outcome $x$ with probability $p(x)>0$, its self-information is

Less probable outcomes carry more self-information. The information entropy of a discrete random variable $X$ is the expected value of this quantity:

with $0\log_2 0$ defined as zero. Base-two logarithms express entropy in bits; natural logarithms express it in nats. Entropy measures average uncertainty before an outcome is observed, not the length of every individual message. (ocw.mit.edu)

A fair coin has one bit of entropy per toss, whereas a coin with a certain outcome has zero. For $n$ possible outcomes, entropy is at most $\log_2 n$, attained by the uniform distribution. Dependence between successive symbols can reduce uncertainty: predictable sequences require fewer bits per symbol than their individual symbol frequencies alone suggest. For suitable stationary sources, this long-run uncertainty is described by the entropy rate. (people.math.harvard.edu)

Dependence and information measures

Conditional entropy $H(X\mid Y)$ measures the average uncertainty remaining about $X$ when $Y$ is known. For discrete variables with finite entropies, mutual information is

It quantifies how much observing one variable reduces uncertainty about the other. Mutual information is symmetric and nonnegative, and equals zero exactly when the variables are independent. It detects statistical dependence, not necessarily causation. (ocw.mit.edu)

More generally, mutual information is the Kullback–Leibler divergence between the joint distribution and the product of its marginals:

The data-processing inequality states that if $X\to Y\to Z$ forms a Markov chain, then $I(X;Z)\leq I(X;Y)$. Processing an observation without access to additional information about the source cannot increase its mutual information with that source, although it may produce a more convenient representation. (ocw.mit.edu)

Compression and source coding

Data compression removes redundancy from representations. Lossless compression permits exact reconstruction; lossy compression permits specified reconstruction errors. Shannon’s source coding theorem gives entropy an operational interpretation: for a discrete memoryless source, optimal average lossless code lengths per symbol approach its entropy as block length increases. The bound concerns average performance under a source distribution, not a guarantee that every possible file becomes shorter. (ocw.mit.edu)

For a finite source alphabet, Huffman coding minimizes average length among binary prefix codes assigning one codeword to each symbol. Coding blocks of symbols can reduce the per-symbol overhead caused by integer codeword lengths. Arithmetic coding instead represents sequences through successively refined probability intervals. Universal compression methods address settings in which the source distribution is not known beforehand. (ocw.mit.edu)

Noisy channels and capacity

Channel capacity is the supremum of rates achievable with decoding error tending to zero. For a discrete memoryless channel with transition probabilities $p(y\mid x)$,

measured in bits per channel use when base-two logarithms are used. The maximization selects the input distribution best suited to the channel. Channels with power or other input constraints require corresponding restrictions on this optimization. (ocw.mit.edu)

The noisy-channel coding theorem establishes that rates below capacity can achieve arbitrarily small error probabilities with sufficiently long codes. Rates above capacity cannot achieve vanishing error under the theorem’s assumptions. Error-correcting codes introduce structured redundancy to distinguish messages despite corrupted symbols. Compression and error correction therefore serve different purposes: one removes unnecessary redundancy, while the other adds redundancy for reliability. These asymptotic limits do not by themselves specify practical decoding complexity or latency. (ocw.mit.edu)

Lossy representation and statistical applications

Rate-distortion theory characterizes the minimum encoding rate compatible with an allowed average distortion. For a memoryless source and distortion function $d(x,\hat{x})$,

The chosen distortion function defines what counts as an acceptable reconstruction; different criteria produce different limits. The theory supplies benchmarks for quantization and lossy representation rather than a universal measure of perceived quality. (ocw.mit.edu)

Information measures also connect communication theory with statistics and machine learning. Cross-entropy satisfies $H(P,Q)=H(P)+D_{\mathrm{KL}}(P\|Q)$, linking expected negative log-likelihood to distributional mismatch. Consequently, fitting a probabilistic model by maximum likelihood minimizes cross-entropy against the empirical distribution. These quantities describe performance relative to specified distributions; estimating them from finite observations is a separate statistical problem. (onlinelibrary.wiley.com)