Starting point: Encodings, decoders and conditioning from the card example; probability and logarithms are developed through coding examples.
Keep in view: A biased binary source and a binary channel that sometimes flips a bit.
We can now describe what a receiver knows. Probabilities record his expectations before an observation, conditioning updates them afterwards, and the best decoder follows from the updated numbers. All of that concerned a single card and a single report.
Real messages are long, and real channels are used many times. Two questions follow that one report cannot answer. How many bits does it take to describe what a source produces? And how many bits can pass through a noisy channel per use? To answer them we first need joint probabilities for pairs of values, and independence for repeated uses. Counting the likely messages then gives entropy, the cost of description. Adding noise forces redundancy, and comparing what a channel output reveals with what it leaves uncertain gives the rate a channel can carry.
2.1 Probability and Correlation
A channel takes an input value and produces an output value, so we must describe two uncertain values at once. How should we describe a pair, and when does one value tell us about the other? We start from a noisy wire and tabulate its input–output pairs. Reading the table in different directions gives the joint, marginal and conditional probabilities. Asking when the output tells Bob nothing then defines independence, which is the assumption that lets us treat long messages.
Alice sends one bit to Bob through a wire. She chooses 0 and 1 equally often. The wire is noisy: on one quarter of uses it flips the bit, whatever the bit was. Bob reads the output. What does the output tell him about the input?
We count, as we did with the cards. Imagine 8 uses in the model's proportions. Alice sends 0 four times; one of those is flipped, so three arrive as 0 and one as 1. The same happens to her four 1s.
Expected counts in 8 uses of a wire that flips one bit in four
Input
Output 0
Output 1
Total
0
3
1
4
1
1
3
4
Total
4
4
8
We need names for the uncertain values. Let \(X\) stand for the input and \(Y\) for the output. A lowercase letter names a particular value: \(x\) can be 0 or 1. An uncertain value with given probabilities is called a random variable.
Each cell of the table divided by 8 is the probability that both things happen. This is the joint probability \(p(x,y)\):
How often does the output equal 0, whatever the input was? We add the first column, \(3/8+1/8=1/2\). In symbols, \(p(y)=\sum_x p(x,y)\), where the sum runs over the allowed inputs \(x=0\) and \(x=1\). A probability obtained this way, by adding over the value we ignore, is a marginal probability.
Now Bob sees output 0. As with the red lamp, he keeps only the trials consistent with what he saw. Of the 4 trials with output 0, 3 had input 0. So \(p(X=0\mid Y=0)=3/4\). In general the conditional probability is
\[p(x\mid y)=\frac{p(x,y)}{p(y)}\qquad(p(y)>0).\]
The wire itself is described by conditional probabilities in the other direction. Given input \(x\), it gives the same bit with probability \(1-e\) and the flipped bit with probability \(e\). Here \(e=1/4\). This wire is called a binary symmetric channel. Rearranging the conditional rule gives \(p(x,y)=p(x)\,p(y\mid x)\): Alice's choice probability times the wire's response. For example, \(p(0,0)=\tfrac12\cdot\tfrac34=\tfrac38\).
The table also exposes a trap. Taken separately, the input and the output each look like a fair coin. Yet they agree on 6 of every 8 trials. So the two marginal distributions do not determine the joint one. A wire that ignored its input and printed a fresh fair coin would have the same marginals and no agreement beyond chance.
The coin-printing wire suggests a question. When does the output tell Bob nothing at all about the input?
Seeing \(y\) tells him nothing exactly when it leaves his probabilities unchanged: \(p(x\mid y)=p(x)\) for every \(x\) and \(y\). Multiplying both sides by \(p(y)\) turns this into a condition on the joint table,
\[p(x,y)=p(x)\,p(y).\]
Two random variables satisfying this for every pair of values are independent. Otherwise they are correlated.
Test our wire. With \(e=1/4\), \(p(0,0)=3/8\) but \(p(0)p(0)=1/4\), so input and output are correlated. Now let the wire flip with \(e=1/2\). Every cell becomes \(1/4\), which equals the product of the marginals. The output is then independent of the input, and Bob may as well not look. At the other extreme, with \(e=0\), the pair is 00 or 11 with equal probability. Each bit alone is still fair, but reading one removes all uncertainty about the other.
Independence matters most when a source is used many times. Suppose a source emits 1 with probability \(1/4\) and 0 otherwise, and suppose each emission is independent of the others. Then probabilities of strings multiply. The string 0010 has probability \((3/4)^3(1/4)=27/256\). Without that assumption we could not compute it from the single-symbol probabilities.
The assumption is substantive. A source with memory might tend to repeat its last symbol, so that 0000 and 1111 are more likely than the product rule says. Our results about long strings all assume independent, identically distributed uses. A source with memory needs its own analysis.
Problems
Problem 2.1. For the fair-input flip channel with e=1/4, what is p(X=0 | Y=0)?
Worked solution
The joint probability is 3/8 and the output-zero probability is 1/2. Dividing gives 3/4. A fair output does not mean the input and output are independent.
2.2 Entropy and Compression
We left the cards with an unmeasured uncertainty. Now that probabilities can be assigned to whole strings, we can ask how many bits a description costs. We start from equally likely messages, where counting yes-or-no questions gives a logarithm. Unequal probabilities then give each message its own cost, and averaging the cost gives entropy. Finally, long strings from an independent source show that entropy is also the rate at which such strings can be compressed.
Suppose Alice picks one of 8 equally likely messages. How many yes-or-no questions does Bob need to identify it? Each well-chosen question splits the remaining candidates in half: 8, then 4, then 2, then 1. So he needs 3 questions, and Alice can send the 3 answers as 3 bits.
With \(N=2^k\) equally likely messages the same halving takes \(k\) questions. The number \(k\) with \(2^k=N\) is the base-two logarithm, written \(\log_2N\). So \(\log_28=3\), and \(\log_2 1=0\): one certain message needs no questions.
What if the messages are not equally likely? Take four messages A, B, C, D with probabilities \(1/2,1/4,1/8,1/8\). A fixed two-bit label for each costs 2 bits. Can Bob do better on average? He can first ask "Is it A?". Half the time the answer is yes, and he is done after one question. Otherwise he asks "Is it B?", and if not, "Is it C?". Writing yes as 0 and no as 1, the answer records are
The average number of bits is \(\tfrac12\cdot1+\tfrac14\cdot2+\tfrac18\cdot3+\tfrac18\cdot3=\tfrac74\), which beats 2.
Look at the lengths. A message of probability \(1/2\) took 1 bit, one of probability \(1/4\) took 2, and one of probability \(1/8\) took 3. In each case the length is \(-\log_2p\). This number is the information content of an outcome of probability \(p\). Rare outcomes carry more of it. It also adds correctly: for two independent outcomes the probabilities multiply, so their information contents add.
The average information content of a source is its entropy,
\[H(X)=-\sum_x p(x)\log_2p(x).\]
A term with \(p(x)=0\) counts as zero, since an impossible message costs nothing on average. For our four messages \(H(X)=7/4\), exactly the average length of the question code. That exact match happens because every probability is a power of one half, so every \(-\log_2p\) is a whole number. For other probabilities the lengths must be rounded up, and a one-symbol code can only come close.
Can any code do better than \(H(X)\) on average? We quote the answer without proof: no code that can be decoded without ambiguity has average length below \(H(X)\). This is part of Shannon's source coding theory.
Why did we need the question structure at all? Bob receives a stream of bits with no spaces. A first 0 completes A. A first 1 means more is coming; 10 completes B, while 11 needs a third bit. He can split the stream as it arrives because no codeword begins another codeword. A code with this property is a prefix code.
For any binary source we write \(h_2(q)=-q\log_2q-(1-q)\log_2(1-q)\), the binary entropy. But a single symbol cannot be sent in 0.81 of a bit. One symbol needs a whole bit, so the question code gains nothing here. Can long strings do better?
Suppose the source runs \(n\) times, with independent uses. A long string will usually contain about \(n/4\) ones. That a long run's fraction of ones settles near its probability is the law of large numbers, which we quote as a standard result of probability theory. Call strings with about \(n/4\) ones typical.
How likely is one typical string? Its probability is a product of \(n/4\) factors of \(1/4\) and \(3n/4\) factors of \(3/4\). Taking \(\log_2\),
So each typical string has probability about \(2^{-nh_2(1/4)}\). The total probability of all typical strings is at most 1. Hence there are at most about \(2^{nh_2(1/4)}\) of them. Alice can number them and send the number, which takes about \(nh_2(1/4)\approx0.81n\) bits instead of \(n\). The rare atypical strings can be sent with a flag and the full string, or declared a failure.
How rare is "rare" for small \(n\)? With \(n=3\), strings with zero or one 1 have total probability \((3/4)^3+3(1/4)(3/4)^2=54/64\approx0.84\). The atypical strings still carry 16% of the probability. The saving only becomes reliable as \(n\) grows.
Shannon's noiseless coding theorem makes this precise for independent repetitions: any rate above \(H\) bits per symbol can be reached with failure probability tending to zero, and no rate below \(H\) can. We cite this theorem and have only shown the counting behind it. It is a statement about long blocks. It does not say that one biased bit fits into 0.81 of a physical bit.
Problems
Problem 2.2. Can 0,01,1 be used as a prefix code?
Worked solution
No. The first word prefixes the second. A concatenation such as 01 can be ambiguous without extra framing.
2.3 Noisy Communication
Compression removes redundancy because the source is predictable. A noisy wire pushes the other way: to survive flips, a message seems to need extra bits. How much extra? We first protect one bit by repeating it and compute what that costs. Then we ask how much one channel output reveals about its input. That quantity, the mutual information, sets the rate a channel can carry reliably.
Alice's wire flips each bit independently with probability \(e\). How can she make Bob's error smaller than \(e\)?
A first attempt is to send each bit three times: 0 as 000 and 1 as 111. Bob takes a majority vote. One flip is outvoted, so Bob fails only when two or three positions flip.
Why does three-fold repetition help, and by how much? There are three ways to flip exactly two positions: 110, 101 and 011. Because flips are independent, each has probability \(e^2(1-e)\). Flipping all three has probability \(e^3\). These four events cannot happen together, so their probabilities add:
\[p(\text{fail})=3e^2(1-e)+e^3=3e^2-2e^3.\]
At \(e=0.1\) this is \(0.027+0.001=0.028\), well below 0.1. The coefficient 3 counts the positions, and the independence assumption is what let us multiply.
The improvement has a price. Three uses of the wire now carry one bit of Alice's message. The rate of a code is the number of message bits divided by the number of channel uses, here \(1/3\). Repetition trades rate for reliability.
Longer repetition codes make the error smaller still, but their rate falls towards zero. Must reliable communication always cost more and more uses per bit?
To answer, we first ask how much one output tells Bob about one input. Before looking, his uncertainty about a fair input is \(H(X)=1\) bit. After seeing \(y\), the input is the same bit with probability \(1-e\) and the other bit with probability \(e\). His remaining uncertainty is \(h_2(e)\), whichever \(y\) he saw. The average uncertainty left after reading the output, \(H(X\mid Y)=\sum_y p(y)\,H(X\mid Y=y)\), is the conditional entropy. Here it equals \(h_2(e)\).
The reduction in uncertainty is the mutual information,
\[I(X:Y)=H(X)-H(X\mid Y)=1-h_2(e).\]
At \(e=1/4\) this is about \(0.19\) bits per use. At \(e=1/2\) it is zero, as it must be, because then input and output are independent. At \(e=0\) it is one full bit.
Does this number say anything about codes? Shannon's channel coding theorem says it does, and we quote it here. For independent uses of the binary symmetric channel, every rate below \(1-h_2(e)\) can be reached with block error tending to zero as the blocks grow. No rate above it can. This limit is the channel's capacity. For a general channel the capacity is the largest mutual information over input distributions; for this symmetric channel the fair input achieves it.
So the answer to our question is no. Long, cleverly designed codes keep a fixed positive rate while their error vanishes. Repetition is not such a code: it lowers the error, but at a rate that shrinks to zero. Our calculation evaluated one input distribution and one code. The theorem's proof needs a coding argument that lies beyond this course.
Every rule so far added probabilities of alternatives that exclude one another. Is every uncertainty about a physical carrier of that kind?
Problem 2.3. At e=0, what rate does the three-bit repetition code achieve?
Worked solution
Only 1/3 bit per channel use, despite a channel capacity of one. Being reliable does not make a code rate-optimal.
Transfer problem. A source emits A,B,C,D with probabilities 1/2,1/4,1/8,1/8. Compare a fixed two-bit encoding with the prefix code in the text over 1,000 independent symbols.
Worked solution
The fixed code uses 2,000 bits. The prefix code has expected length 1,750 bits, saving 250 on average. The actual length fluctuates; prefix decoding is exact for every source sequence, rather than merely for typical ones.
Summary
Shannon entropy \(H(X) = -\sum_x p(x)\log_2 p(x)\) measures the expected surprise of a source and sets the asymptotic limit of lossless data compression at \(H(X)\) bits per symbol.
Joint entropy, conditional entropy \(H(X|Y)\), and mutual information \(I(X:Y) = H(X) - H(X|Y)\) quantify how much observing one random variable reduces uncertainty about another.
Shannon’s noisy-channel coding theorem establishes that reliable communication over a discrete memoryless channel is possible up to capacity \(C = \max_{p(x)} I(X:Y)\).
Questions and worked problems
These exercises draw on the whole chapter. Attempt each question before opening a hint, explain your reasoning, then compare it with the worked solution.
Compute the entropy \(H(X)\) in bits for each distribution: (a) \((\frac12,\frac12)\); (b) \((1,0)\); (c) eight equally likely values; (d) \((\frac12,\frac14,\frac14)\). Which distribution is most uncertain per symbol?
Hint 1
\(H=-\sum p\log_2p\), with \(0\log0=0\).
Hint 2
\(-\log_2\frac14=2\).
Worked solution
(a) \(1\) bit. (b) \(0\): the value is certain. (c) \(\log_28=3\) bits. (d) \(\frac12\cdot1+\frac14\cdot2+\frac14\cdot2=1.5\) bits. The eight-value uniform distribution is the most uncertain. Entropy grows with the number of possibilities and is largest when they are equally likely; a prefix code such as \(0,10,11\) attains \(1.5\) bits on average for distribution (d).
Decide whether \(X\) and \(Y\) are independent: (a) \(p(00)=0.4\), \(p(01)=0.1\), \(p(10)=0.4\), \(p(11)=0.1\); (b) \(p(00)=p(11)=0.45\), \(p(01)=p(10)=0.05\).
Hint 1
Find the marginals by summing rows and columns.
Hint 2
Independence requires \(p(x,y)=p(x)p(y)\) for every pair.
Worked solution
(a) \(p(X=0)=p(X=1)=0.5\) and \(p(Y=0)=0.8\), \(p(Y=1)=0.2\). Every joint probability equals the product, for example \(0.5\times0.8=0.4\), so they are independent. (b) Both marginals are \((0.5,0.5)\), but \(p(00)=0.45\neq0.25\), so they are correlated: the bits agree \(90\%\) of the time. Fair marginals say nothing about whether two bits are correlated; only the joint distribution does.
Find the capacity \(1-h_2(e)\) of the binary symmetric channel for \(e=0.1\), \(e=0.5\), and \(e=0.9\). Why does the channel with \(e=0.9\) have the same capacity as the one with \(e=0.1\)?
Hint 1
\(h_2(0.1)\approx0.469\).
Hint 2
\(h_2(e)=h_2(1-e)\).
Worked solution
For \(e=0.1\), capacity is \(1-0.469\approx0.531\) bits per use. For \(e=0.5\) it is \(0\): the output is independent of the input. For \(e=0.9\) it is again \(0.531\), because \(h_2(0.9)=h_2(0.1)\). A channel that flips \(90\%\) of bits is a reliable channel followed by a known NOT, which the receiver can undo. What limits communication is uncertainty about whether a flip occurred, not the flips themselves.
A source emits A, B, C, D with probabilities \(0.4,0.3,0.2,0.1\). (a) Check that the code A\(=0\), B\(=10\), C\(=110\), D\(=111\) is a prefix code and compute its average length. (b) Compute the entropy. (c) Decode the string 1100111010.
Read bits from the left, stopping as soon as a codeword is complete.
Worked solution
(a) No codeword begins another codeword, so it is a prefix code. The average length is \(0.4\cdot1+0.3\cdot2+0.2\cdot3+0.1\cdot3=1.9\) bits. (b) \(H\approx0.4(1.322)+0.3(1.737)+0.2(2.322)+0.1(3.322)\approx1.846\) bits. The code is about \(0.05\) bits per symbol above the entropy; since these probabilities are not powers of one half, no one-symbol code reaches \(H\) exactly, and coding blocks of symbols can close the gap. (c) \(110\,|\,0\,|\,111\,|\,0\,|\,10\) gives C A D A B.
Extend the repetition code to five uses: send \(00000\) or \(11111\) and decode by majority. For independent flips with \(e=0.1\), compute the failure probability and the rate. Compare with the three-use code and with the capacity \(0.531\). What does the comparison suggest about repetition codes?
Hint 1
Failure means three or more flips among five.
Hint 2
\(\binom53=10\), \(\binom54=5\).
Worked solution
Failure requires at least three flips: \(10e^3(1-e)^2+5e^4(1-e)+e^5=0.0081+0.00045+0.00001\approx0.0086\). The rate is \(1/5\). The three-use code fails with probability \(0.028\) at rate \(1/3\). Each extra pair of repetitions lowers the error but also the rate, and driving the error to zero this way drives the rate to zero. The capacity \(0.531\) says that much better codes exist: for any rate below \(0.531\), long block codes make the error as small as desired at a fixed rate. Repetition illustrates redundancy, not efficient coding.
For a fair input bit through the flip channel with \(e=1/4\), the joint probabilities are \(3/8,1/8,1/8,3/8\). (a) Find \(p(x\mid y)\) for each output. (b) Compute \(H(X\mid Y)\) and \(I(X:Y)\). (c) Compare with a channel that copies the bit perfectly and with one whose output is a fresh fair coin.
Hint 1
Given \(Y=0\), the input is \(0\) with probability \(3/4\).
Hint 2
\(h_2(1/4)\approx0.811\).
Worked solution
(a) Given \(Y=0\), \(p(X=0\mid Y=0)=(3/8)/(1/2)=3/4\); given \(Y=1\), \(X=1\) with probability \(3/4\). (b) Each output leaves uncertainty \(h_2(1/4)\approx0.811\), so \(H(X\mid Y)\approx0.811\) and \(I(X:Y)\approx1-0.811=0.189\) bits. (c) A perfect copy gives \(H(X\mid Y)=0\) and \(I=1\) bit; an independent coin gives \(H(X\mid Y)=1\) and \(I=0\). Although Bob guesses correctly \(75\%\) of the time with this channel, it conveys less than a fifth of a bit per use, because the remaining uncertainty is large.
A source emits \(n=100\) independent bits, each \(1\) with probability \(\frac14\). (a) Show that every string with exactly \(25\) ones has probability \(2^{-nh_2(1/4)}\approx2^{-81.1}\). (b) There are \(\binom{100}{25}\approx2^{77.7}\) such strings: what is their total probability? (c) Strings with between \(20\) and \(30\) ones number about \(2^{85.4}\) and carry probability about \(0.80\). What does this say about compression at \(n=100\) compared with the asymptotic \(81.1\) bits?
Total probability is the count times the probability of each string.
Worked solution
(a) \(\log_2\big[(\frac14)^{25}(\frac34)^{75}\big]=25(-2)+75(-0.415)\approx-81.1=-100\,h_2(\frac14)\). (b) \(2^{77.7}\times2^{-81.1}=2^{-3.4}\approx0.09\): the single most likely composition holds only about \(9\%\) of the probability. (c) Labelling the \(2^{85.4}\) strings with \(20\) to \(30\) ones takes about \(86\) bits and covers \(80\%\) of outputs, against \(100\) bits uncompressed. Covering more probability needs a wider window and more bits. Only as \(n\) grows does the needed label length per bit approach \(h_2(\frac14)\approx0.811\) with vanishing error; at \(n=100\) the typical set is still blurred.
A student claims: “A good compressor shortens every file.” Use counting to show that no lossless code maps every \(n\)-bit string to a strictly shorter string. How, then, do compressors work?
Hint 1
How many bit strings have length less than \(n\), including the empty string?
Hint 2
Lossless means different inputs get different outputs.
Worked solution
There are \(2^n\) strings of length \(n\), but only \(1+2+4+\cdots+2^{n-1}=2^n-1\) strings shorter than \(n\). A lossless code must give different outputs to different inputs, so it cannot fit \(2^n\) inputs into \(2^n-1\) shorter outputs: at least one string is not shortened. Compressors work by giving short codewords to likely strings and longer ones to unlikely strings, so the average length drops for a particular source. Entropy measures what is achievable on average for that source; compression is a bet on the distribution, not a shrinking of every message.
A prefix code with codeword lengths \(\ell_1,\dots,\ell_m\) must satisfy the Kraft inequality \(\sum_i2^{-\ell_i}\le1\). (a) Explain it by imagining each codeword as reserving all infinite bit strings that begin with it. (b) Check it for \(0,10,110,111\). (c) Show that no prefix code has lengths \(1,1,2\), which explains why \(0,01,1\) fails.
Hint 1
A codeword of length \(\ell\) begins a fraction \(2^{-\ell}\) of all long strings.
Hint 2
The prefix condition means the reserved sets do not overlap.
Worked solution
(a) A codeword of length \(\ell\) is the beginning of a fraction \(2^{-\ell}\) of all long bit strings. Because no codeword begins another, these fractions belong to disjoint sets of strings, so they add to at most \(1\). (b) \(\frac12+\frac14+\frac18+\frac18=1\): the code uses all available space, which is why its average length can equal the entropy for the matching dyadic distribution. (c) Lengths \(1,1,2\) give \(\frac12+\frac12+\frac14>1\), so no prefix code has them. In \(0,01,1\), the codeword \(0\) begins \(01\), and the string \(01\) is ambiguous: A followed by C, or B.
For two random variables, \(H(X,Y)=-\sum_{x,y}p(x,y)\log_2p(x,y)\). (a) Show that \(H(X,Y)=H(X)+H(Y)\) when \(X\) and \(Y\) are independent. (b) Compute \(H(X,Y)\), \(H(X)\), and \(H(Y)\) for the fair correlated pair that is \(00\) or \(11\) with equal probability, and for the flip channel with \(e=1/4\). (c) Interpret \(H(X)+H(Y)-H(X,Y)\).
Hint 1
For independent variables, \(\log p(x,y)=\log p(x)+\log p(y)\).
Hint 2
For the flip channel, the four joint probabilities are \(3/8,1/8,1/8,3/8\).
Worked solution
(a) If \(p(x,y)=p(x)p(y)\), then \(-\sum p(x,y)[\log_2p(x)+\log_2p(y)]=H(X)+H(Y)\), using \(\sum_yp(x,y)=p(x)\). (b) Correlated pair: \(H(X,Y)=1\) bit, while \(H(X)=H(Y)=1\). Flip channel: \(H(X,Y)=2\cdot\frac38\log_2\frac83+2\cdot\frac18\cdot3\approx1.061+0.75=1.811\), with \(H(X)=H(Y)=1\). (c) The difference is \(1\) bit for the correlated pair and about \(0.189\) bits for the channel: exactly \(I(X:Y)\). Correlation makes the pair less uncertain than its parts taken separately, and mutual information measures the overlap.