A Complete Guide to Shannon Information Theory

Shannon information theory does not ask what a message means. It asks:

In the presence of uncertainty, how can information be measured, and how quickly can it be compressed or transmitted reliably?

Claude Shannon's 1948 paper, A Mathematical Theory of Communication, gave communication, compression, noise, and coding a common mathematical framework.

1. The decisive abstraction

A communication system can be represented as:

$$\text{source}\rightarrow\text{encoder}\rightarrow\text{channel} \rightarrow\text{decoder}\rightarrow\text{receiver}$$

For a text message, the source is the text, the encoder turns it into bytes, packets, and physical signals, the channel is the network, noise includes loss and bit flips, and the decoder reconstructs the message.

Shannon deliberately sets meaning aside. The mathematical questions are:

1. How uncertain is the receiver before the message arrives?
2. How much uncertainty disappears after it arrives?
3. What is the minimum number of bits needed to represent it?
4. In a noisy channel, how quickly can it be transmitted reliably?

The central idea is that information is not the symbol itself; it is the uncertainty removed by observing the symbol.

2. Surprisal: unlikely events carry more information

For an event $x$ with probability $p(x)$, its self-information, or surprisal, is:

$$I(x)=-\log_2p(x)$$

The unit is the bit. An event with probability 1 carries zero new information. One outcome of a fair coin carries:

$$-\log_2\frac{1}{2}=1\text{ bit}$$

An event with probability $10^{-6}$ carries about $19.93$ bits.

The logarithm is important because independent probabilities multiply while information should add. If $x$ and $y$ are independent:

$$p(x,y)=p(x)p(y)$$

and therefore:

$$I(x,y)=-\log p(x,y)=I(x)+I(y)$$

3. Entropy: average information produced by a source

Taking the expectation of surprisal gives entropy:

$$H(X)=-\sum_xp(x)\log_2p(x)$$

Entropy can be read as average uncertainty, average surprise, average information, or the lower bound on the average number of bits needed by an ideal code.

A fair coin has entropy 1 bit. For a heavily biased coin with $p(0)=0.99$ and $p(1)=0.01$:

$$H(X)=-0.99\log_2 0.99-0.01\log_2 0.01\approx0.081$$

The output still takes one of two values, but it is highly predictable. Over long sequences it can be represented using far less than one bit per toss.

For $n$ possible outcomes, entropy is maximized by the uniform distribution:

$$H(X)=\log_2n$$

Entropy is therefore not a strict synonym for disorder. It is uncertainty under a probability distribution.

4. The source coding theorem

How far can a random source be compressed? Its average code length cannot remain below $H(X)$, but for sufficiently long sequences it can be made arbitrarily close to $H(X)$.

Suppose $p(A)=0.9$ and $p(B)=0.1$. A direct one-bit code assigns one bit to every character, but the source entropy is:

$$H(X)=-0.9\log_2 0.9-0.1\log_2 0.1\approx0.469$$

The theoretical average is about $0.469$ bits per symbol because only a comparatively small set of typical sequences carries most of the probability mass.

Compression does not mean discarding information. Lossless compression exploits non-uniformity and redundancy. Huffman coding, arithmetic coding, Lempel-Ziv, ZIP, and learned compressors all give shorter representations to more probable events.

This connects directly to language models. If a model assigns probability $p(x)$ to the true token, its ideal code length is $-\log_2p(x)$. Cross-entropy can therefore be interpreted as the average number of bits needed to encode data using the model.

5. Joint and conditional entropy

The joint entropy of $X$ and $Y$ is:

$$H(X,Y)=-\sum_{x,y}p(x,y)\log p(x,y)$$

It obeys the chain rule:

$$H(X,Y)=H(X)+H(Y|X)$$

First describe $X$, then describe the uncertainty still left in $Y$ once $X$ is known. If $Y=X$, then $H(Y|X)=0$. If $X$ and $Y$ are independent, then $H(Y|X)=H(Y)$.

6. Mutual information

Mutual information measures how much observing one variable reduces uncertainty about another:

$$I(X;Y)=H(X)-H(X|Y)$$

Equivalently:

$$I(X;Y)=H(X)+H(Y)-H(X,Y)$$

If $X$ and $Y$ are independent, $I(X;Y)=0$. If $Y=X$, then $I(X;Y)=H(X)$. A noisy copy lies between those cases.

Unlike correlation, mutual information is not limited to linear dependence. For example, if $Y=X^2$ and $X$ is symmetric around zero, linear correlation may vanish even though $Y$ is fully determined by $X$.

7. KL divergence and cross-entropy

The Kullback-Leibler divergence is:

$$D_{\mathrm{KL}}(P\|Q)=\sum_xP(x)\log\frac{P(x)}{Q(x)}$$

It is the extra coding cost incurred when data really follow $P$ but are encoded using $Q$. It is non-negative and equals zero only when the distributions agree, but it is not a true distance: it is asymmetric and does not generally satisfy the triangle inequality.

Cross-entropy is:

$$H(P,Q)=-\sum_xP(x)\log Q(x)$$

and:

$$H(P,Q)=H(P)+D_{\mathrm{KL}}(P\|Q)$$

When the data distribution $P$ is fixed, minimizing cross-entropy is equivalent to minimizing $D_{\mathrm{KL}}(P\|Q)$. This is why cross-entropy appears throughout classification and language modeling.

8. Noise and the channel model

Now consider:

$$X\rightarrow\text{channel}\rightarrow Y$$

Because of noise, the received $Y$ may differ from the transmitted $X$. In a binary symmetric channel, each bit flips with probability $\epsilon$:

$$P(Y\neq X)=\epsilon$$

Can communication still approach zero error? Shannon's answer is yes, provided the transmission rate stays below the channel capacity.

9. Channel capacity

Channel capacity is:

$$C=\max_{p(x)}I(X;Y)$$

It is the largest amount of information that can be transmitted reliably per channel use. The maximization over input distributions matters because different input distributions may use the channel with different efficiency.

For a binary symmetric channel:

$$C=1-H_2(\epsilon)$$

where:

$$H_2(\epsilon)=-\epsilon\log_2\epsilon-(1-\epsilon)\log_2(1-\epsilon)$$

At $\epsilon=0$, capacity is 1 bit per use. At $\epsilon=0.5$, output is independent of input and capacity is zero. At $\epsilon=1$, every bit flips deterministically and capacity returns to 1: the receiver can simply invert every bit.

10. The noisy-channel coding theorem

Let $C$ be channel capacity and $R$ the communication rate.

• If $R<C$, codes exist whose error probability approaches zero as block length grows.
• If $R>C$, no code can make communication arbitrarily reliable.

Noise does not make reliable communication impossible. It creates a rate limit.

Reliability comes from structured redundancy. Repetition codes show the basic idea, while Hamming, Reed-Solomon, Turbo, LDPC, and Polar codes achieve far better efficiency. Shannon did not construct the best code; he proved that good codes must exist and that a hard limit separates the possible from the impossible.

11. Source coding and channel coding point in opposite directions

Source coding removes predictable redundancy:

$$\text{source data}\rightarrow\text{shorter representation}$$

Channel coding adds structured redundancy for recovery:

$$\text{compressed data}\rightarrow\text{error-correctable representation}$$

A complete system often looks like:

$$\text{data}\xrightarrow{\text{compression}}\text{compact form} \xrightarrow{\text{error correction}}\text{robust form}$$

The two operations are not contradictory: one removes redundancy that carries no new source information, while the other adds redundancy designed to reveal transmission errors.

12. Source-channel separation

If a source has entropy rate $H$ and a channel has capacity $C$, reliable communication is possible in principle when:

$$H<C$$

Optimal compression and optimal channel coding may be designed separately. This separation is one foundation of modular digital communication.

Finite block lengths, strict latency limits, and semantic communication can make joint source-channel methods preferable in practice, but they do not erase the asymptotic theorem.

13. Typical sets

Take $n$ independent samples $X_1,\dots,X_n$ from $p(x)$. Most probability mass concentrates in a typical set containing roughly:

$$2^{nH(X)}$$

sequences, each with probability about:

$$2^{-nH(X)}$$

The full space may contain $|\mathcal{X}|^n$ sequences, but only about $2^{nH(X)}$ are needed to cover almost all probability. Distinguishing them takes roughly $nH(X)$ bits. This is the intuition behind entropy as the compression limit.

14. Information theory is not a theory of meaning

Two sentences can have similar Shannon information because they have similar probability and symbol structure, even if one is trivial and the other is existentially important.

Shannon information does not measure truth, meaning, value, importance, or human understanding. It measures the statistical uncertainty removed by a message under a chosen probability model.

That limitation is also the source of the theory's generality: once semantics are excluded, the same mathematics can describe text, radio signals, storage, genomes, and model predictions.

15. Connections to machine learning

Cross-entropy and maximum likelihood

The common supervised loss:

$$\mathcal{L}=-\log p_\theta(y|x)$$

is the code length assigned to the true label by the model. Maximizing log likelihood is equivalently minimizing the encoded length of the observations under the model.

Language models and perplexity

For average token cross-entropy:

$$H=-\frac{1}{N}\sum_{i=1}^{N}\log_2p(x_i|x_{<i})$$

perplexity is:

$$\mathrm{PPL}=2^H$$

If $H=3$, then $\mathrm{PPL}=8$, roughly the uncertainty of choosing among eight equally likely candidates at each position.

Representation learning

The information bottleneck suggests keeping information about the target while discarding irrelevant detail:

$$\max I(Z;Y)-\beta I(Z;X)$$

The expression is conceptually useful, but mutual information in deterministic networks and continuous spaces can be difficult or ill-defined to estimate. It should not be applied too literally.

Contrastive and generative learning

InfoNCE is often interpreted through a lower bound on mutual information, although contrastive learning cannot be reduced to “maximize mutual information” alone.

The variational autoencoder objective contains:

$$\mathbb{E}_{q(z|x)}[\log p(x|z)] -D_{\mathrm{KL}}(q(z|x)\|p(z))$$

The KL term regulates how far the latent distribution moves from its prior. Similar ideas of likelihood, entropy, and coding run through diffusion models, flow models, and language models.

16. Information depends on the observer's model

The quantity $-\log p(x)$ depends on the probability model used to assign $p(x)$. A weather event may surprise someone who knows nothing about the climate and be entirely expected to someone with a precise forecast.

Information is not solely an intrinsic property of the message. It is defined relative to a model.

This motivates anomaly scores such as $-\log p_\theta(x)$, but also explains likelihood paradoxes: deep generative models can assign high likelihood to out-of-distribution inputs because likelihood reflects low-level statistics, not necessarily semantic normality.

17. What made Shannon's theory revolutionary

Three consequences matter beyond the entropy formula:

1. Information can be separated from its physical carrier. Text, sound, images, and video can all become bits.
2. Noise does not prevent reliable communication. Coding can drive logical error rates arbitrarily low below capacity.
3. Engineering has provable limits. Compression and communication have boundaries that no clever algorithm can cross.

Communication became a mathematical discipline with explicit limits rather than only an empirical craft.

18. The core quantities at a glance

Quantity	Formula	Interpretation
Surprisal	$I(x)=-\log p(x)$	How unexpected one event is
Entropy	$H(X)=\mathbb{E}[-\log p(X)]$	Average uncertainty in a random variable
Conditional entropy	$H(X\mid Y)$	Uncertainty left in $X$ after observing $Y$
Mutual information	$I(X;Y)=H(X)-H(X\mid Y)$	Uncertainty about $X$ removed by $Y$
KL divergence	$D_{\mathrm{KL}}(P\|Q)$	Extra coding cost from using the wrong model
Channel capacity	$C=\max_{p(x)}I(X;Y)$	Maximum reliable information per channel use

19. Two conclusions to keep

The compression limit is:

$$\boxed{\text{The limiting average length of lossless codes is entropy.}}$$

The communication limit is:

$$\boxed{\text{Below channel capacity, arbitrarily reliable communication is possible.}}$$

Entropy describes how quickly a source produces information. Capacity describes how quickly a channel can carry it. When production stays below transport capacity, reliable communication is possible.