Probability for Coding

The previous chapter, Why Codes Exist, computed every error probability with two moves, multiplying the chances of bit flips that have nothing to do with each other and adding the chances of error patterns that cannot happen together. Those moves gave the decoded error of the repetition code, $3p^2 - 2p^3$, and the miss rate of a parity check, because every situation was small enough to list. A 72-bit memory word has $2^{72}$ possible error patterns and a frame of a thousand bits has $2^{1000}$, and no list reaches that far.

This chapter turns the two moves into a toolkit that scales. It starts with events on three bits, where every probability can be checked by hand, then counts errors with the binomial distribution, summarizes a count by its expectation and variance, and proves the law of large numbers, which explains why a measured bit error rate settles down to the true one. The Gaussian distribution enters as the model of noise on a voltage, with the Q-function as its tail. The chapter closes with the union bound and the Chernoff bound, the two inequalities the rest of the book leans on whenever an exact sum is out of reach.

Every theorem is proved, after a number that can be checked by hand. The algebra needed is powers, the exponential function and the natural logarithm, and the Gaussian section explains the one idea from calculus it uses, the integral as an area. Every number in the chapter is recomputed by ch02_probability_for_coding.py, in the python/ folder of the companion repository ecc-book-lab, which prints each value beside the one the text states and stops at the first disagreement. The charts are drawn by ch02_charts.py in the same folder.

01.Events on Three Bits

Send the codeword 000 of the three-bit repetition code over the binary symmetric channel of the previous chapter, $\text{BSC}(0.1)$, which flips each bit with probability $p = 0.1$ and leaves it alone with probability $0.9$. The receiver sees one of eight patterns. A pattern with $w$ flipped bits has probability $0.1^w \, 0.9^{3-w}$, so the received word 000 has probability $0.9^3 = 0.729$, each of 100, 010 and 001 has probability $0.1 \times 0.9^2 = 0.081$, each of 110, 101 and 011 has probability $0.1^2 \times 0.9 = 0.009$, and 111 has probability $0.1^3 = 0.001$. The eight numbers add to 1, as they must, because some pattern always arrives.

That list is the whole experiment. Any question about one use of the channel, such as whether the decoder will fail, is answered by adding the probabilities of the patterns where the answer is yes. The vocabulary below names the pieces, so that the same reasoning reaches lists too long to write down.

The set of every possible outcome is the sample space, written $\Omega$, the capital Greek letter omega. Here $\Omega$ holds the eight received patterns. A single outcome is written $\omega$, the lower-case omega, and the statement "$\omega$ belongs to the set $E$" is written $\omega \in E$. An event is any set of outcomes, the set for which some yes-or-no question has the answer yes.

Three facts follow at once. The whole sample space has probability $P(\Omega) = 1$, the empty event has probability 0, and two events $E$ and $F$ that share no outcome, called disjoint, satisfy $P(E \cup F) = P(E) + P(F)$, where $E \cup F$, the union, is the set of outcomes in $E$ or $F$ or both. The last fact holds because each outcome of the union appears in exactly one of the two sums.

Two events on the three bits carry the rest of this section. Event $A$ is "the first bit flipped," the set $\{100, 110, 101, 111\}$, with probability $0.081 + 0.009 + 0.009 + 0.001 = 0.1$, which had to equal $p$ and so checks the list. Event $B$ is "the majority decoder fails," which happens when two or more bits flip, the set $\{110, 101, 011, 111\}$, with probability $3 \times 0.009 + 0.001 = 0.028$, the decoded error of $R_3$ found in the previous chapter. Figure 1 shows both events.

Complements, Intersections and Unions

The complement of an event $B$, written $B^c$ and read "not $B$," is the set of outcomes outside $B$, here the event that the decoder succeeds. Since $B$ and $B^c$ are disjoint and together make up $\Omega$, $P(B^c) = 1 - P(B) = 0.972$. The complement is often the easier side of a question, which is how the previous chapter found the chance of at least one error in a terabyte.

The intersection $A \cap B$ is the set of outcomes in both events. Here it is $\{110, 101, 111\}$, the cases where the first bit flipped and the decoder failed, with probability $0.009 + 0.009 + 0.001 = 0.019$. The union $A \cup B$ is $\{100, 110, 101, 111, 011\}$, with probability $0.081 + 0.009 + 0.009 + 0.001 + 0.009 = 0.109$. Adding $P(A) + P(B) = 0.128$ gives too much, because the three shared outcomes were counted once in each event.

Proof. The union splits into three disjoint pieces, the outcomes in $A$ only, written $A \cap B^c$, the outcomes in both, $A \cap B$, and the outcomes in $B$ only, $A^c \cap B$. Additivity gives $P(A \cup B) = P(A \cap B^c) + P(A \cap B) + P(A^c \cap B)$. The event $A$ splits the same way into $A \cap B^c$ and $A \cap B$, so $P(A) = P(A \cap B^c) + P(A \cap B)$, and likewise $P(B) = P(A^c \cap B) + P(A \cap B)$. Adding the last two equations gives $P(A) + P(B) = P(A \cup B) + P(A \cap B)$, which rearranges to the theorem. $\blacksquare$

The check on the example is $0.1 + 0.028 - 0.019 = 0.109$, which matches the direct sum.

Conditional Probability

Suppose a test reveals that the first bit flipped, and nothing about the other two. The outcomes still possible are those of $A$, totaling 0.1, and the failing ones among them total 0.019. Rescaling the survivors so that they add to 1 gives a failure probability of $0.019 / 0.1 = 0.19$. Direct reasoning agrees, since the decoder now fails unless both other bits arrive intact, so failure has probability $1 - 0.9^2 = 0.19$, up from 0.028.

The opposite case, where the test shows that the first bit arrived intact, gives $P(B \mid A^c) = P(A^c \cap B) / P(A^c)$. The only failing pattern with an intact first bit is 011, so this is $0.009 / 0.9 = 0.01$, which is $p^2$, the chance that both remaining bits flip.

The two conditional probabilities rebuild the unconditional one. Weighting each by the probability of its condition gives $0.19 \times 0.1 + 0.01 \times 0.9 = 0.028$, which is $P(B)$ again.

Proof. Every outcome of $B$ lies in exactly one $A_i$, so $B$ is the disjoint union of the pieces $B \cap A_1, \ldots, B \cap A_m$, and additivity gives $P(B) = \sum_i P(B \cap A_i)$. The definition of conditional probability, multiplied through by $P(A_i)$, says $P(B \cap A_i) = P(B \mid A_i) \, P(A_i)$. Substituting each term gives the theorem. $\blacksquare$

Now reverse the question. Given that the decoder failed, how likely is it that the first bit flipped? The definition gives $P(A \mid B) = P(A \cap B) / P(B) = 0.019 / 0.028 = 19/28 = 0.6786$, up from 0.1, because a failure needs at least two flips, and two of the three two-flip patterns, as well as 111, involve the first bit.

Proof. The definition of conditional probability, applied in both directions, gives $P(A \mid B) \, P(B) = P(A \cap B)$ and $P(B \mid A) \, P(A) = P(A \cap B)$. The two left-hand sides are therefore equal, and dividing by $P(B)$ gives the theorem. $\blacksquare$

Bayes' rule is the step every decoder takes, because a channel gives the probability of what is received given what was sent, while a receiver needs the reverse.

Independence

In the reversal above, learning $B$ changed the probability of $A$. Events for which the knowledge changes nothing are the ones the channel model is built from.

The events $A$ and $B$ fail the test, since $P(A)\,P(B) = 0.1 \times 0.028 = 0.0028$ while $P(A \cap B) = 0.019$. The event $C$, "the second bit flipped," passes it, since $A \cap C = \{110, 111\}$ has probability $0.009 + 0.001 = 0.01 = P(A)\,P(C)$. Flips of different bits are independent, as the channel promises.

For more than two events the definition needs a stronger form. Events $E_1, \ldots, E_n$ are mutually independent when, for every choice of some of them, the probability that all the chosen events occur is the product of their probabilities. The binary symmetric channel assumes this of the events $F_i$, "bit $i$ flipped," each of probability $p$, and that is where the pattern probability of 110 comes from. The event "110 received" is what remains of $F_1 \cap F_2$ after removing $F_1 \cap F_2 \cap F_3$, so

$$P(F_1 \cap F_2 \cap F_3^c) = P(F_1 \cap F_2) - P(F_1 \cap F_2 \cap F_3) = p^2 - p^3 = p^2 (1-p).$$

Mutual independence is genuinely stronger than independence of every pair. At $p = 1/2$, take $F_1$, $F_2$ and the event $G$ that bits 1 and 2 agree. Each has probability $1/2$ and every pair intersects with probability $1/4$, so the three are independent in pairs. Yet all three occur exactly when bits 1 and 2 both flip, with probability $1/4$, not the product $1/8$.

02.Counting Errors with the Binomial Distribution

A decoder usually asks how many bits flipped. A random variable is a rule that assigns a number to every outcome. Let $X$ be the number of flipped bits among the three, so $X(000) = 0$, $X(100) = 1$ and $X(110) = 2$. The event $X = 2$ is the set $\{110, 101, 011\}$, with probability $3 \times 0.009 = 0.027$, and the four values give $P(X=0) = 0.729$, $P(X=1) = 0.243$, $P(X=2) = 0.027$ and $P(X=3) = 0.001$, the last column of the table in the previous chapter.

The formula below does the same job for any number of bits. It uses the factorial $n!$, the product $1 \times 2 \times \cdots \times n$, with $0! = 1$ by convention, and the binomial coefficient $\binom{n}{k}$, read "$n$ choose $k$," which counts the ways to choose $k$ positions out of $n$.

Proof. First the count. Choose the $k$ flipped positions one at a time. There are $n$ choices for the first, $n - 1$ for the second, and so on down to $n - k + 1$ for the last, so there are $n(n-1)\cdots(n-k+1) = n!/(n-k)!$ ordered choices. Each set of $k$ positions is reached in $k!$ of these orders, by the same count applied to its own $k$ positions, so there are $n! / (k!\,(n-k)!)$ distinct sets.

Next one pattern. A pattern with flips in a given set of $k$ positions is the intersection of $k$ events "bit $i$ flipped" and $n - k$ events "bit $i$ did not flip." By mutual independence its probability is the product $p^k (1-p)^{n-k}$, the same for every such pattern.

Finally the sum. The event $X = k$ is the disjoint union of the $\binom{n}{k}$ patterns with exactly $k$ flips, so additivity gives $\binom{n}{k}$ times the common pattern probability. To see that the probabilities add to 1, expand $(x + y)^n$ as a product of $n$ factors $(x + y)$. Each term of the expansion picks $x$ from some of the factors and $y$ from the rest, and the terms that pick $x$ from exactly $k$ factors number $\binom{n}{k}$, which proves the binomial theorem $(x+y)^n = \sum_{k} \binom{n}{k} x^k y^{n-k}$. Setting $x = p$ and $y = 1 - p$ gives $\sum_k P(X = k) = (p + 1 - p)^n = 1$. $\blacksquare$

For $n = 3$ and $p = 0.1$ the formula gives $\binom{3}{2} \, 0.1^2 \, 0.9 = 3 \times 0.009 = 0.027$, as the list did. Table 1 applies it to a byte on a channel with $p = 0.01$.

The table explains two numbers from the previous chapter. A byte holds at least one error with probability $1 - 0.922745 = 0.077255$, which is $1 - 0.99^8$, and almost all of the parity check's miss rate, 0.0026368, is the row $k = 2$, at 0.0026361. Each row is a small correction to the one above it, which is why a code that handles the few most likely error counts handles nearly everything.

The Shape of the Distribution

Figure 2 plots the distribution for a 20-bit block on a poor channel, $p = 0.1$. The bars rise from $P(X = 0) = 0.1216$ to a peak of $0.2852$ at $k = 2$ and then fall, through $0.1901$, $0.0898$ and $0.0319$, down to $0.0004$ at $k = 8$.

The peak is located without computing every bar. Dividing two neighboring values of Equation 4 cancels most of the factorials,

$$\frac{P(X = k+1)}{P(X = k)} = \frac{\binom{n}{k+1}}{\binom{n}{k}} \cdot \frac{p}{1-p} = \frac{n-k}{k+1} \cdot \frac{p}{1-p},$$

because $\binom{n}{k+1} / \binom{n}{k} = \frac{k!\,(n-k)!}{(k+1)!\,(n-k-1)!} = \frac{n-k}{k+1}$. With $n = 20$ and $p/(1-p) = 1/9$, the ratio is $20/9 = 2.22$ at $k = 0$, $19/18 = 1.06$ at $k = 1$ and $18/27 = 0.667$ at $k = 2$, and it keeps shrinking as $k$ grows. The bars grow while the ratio exceeds 1, so the peak is at $k = 2$. For coding the tail matters more, since a code that corrects any four errors in this block fails with probability $P(X \ge 5) = 0.0432$.

03.Expectation and Variance

Two numbers summarize a distribution, where its values sit on average and how far they stray. For the three bits, weighting each count by its probability and adding gives $0 \times 0.729 + 1 \times 0.243 + 2 \times 0.027 + 3 \times 0.001 = 0.3$. Over many uses the flips would average near 0.3, a claim the law of large numbers makes precise, and the answer is $3 \times 0.1$, three bits each contributing 0.1 flips on average. That is no coincidence.

The value $3 \times 0.1$ comes from splitting the count into pieces. For each bit position $i$, define the indicator $X_i$, which is 1 if bit $i$ flipped and 0 if not. The count of flips is the sum of the indicators, $X = X_1 + X_2 + \cdots + X_n$, as Figure 3 shows for one received byte. Each indicator has expectation $1 \times p + 0 \times (1 - p) = p$. What remains is to show that the expectation of a sum is the sum of the expectations.

The proof rests on a second way to compute an expectation, one outcome at a time instead of one value at a time. Each value $k$ collects the outcomes $\omega$ with $X(\omega) = k$, so $k \, P(X = k) = \sum_{\omega : X(\omega) = k} X(\omega) \, P(\omega)$, where the sum runs over the outcomes with that value. Adding over all values reaches every outcome exactly once, so

$$E[X] = \sum_{\omega \in \Omega} X(\omega) \, P(\omega).$$

Proof. By the outcome-by-outcome form, $E[X + Y] = \sum_{\omega} \bigl(X(\omega) + Y(\omega)\bigr) P(\omega) = \sum_{\omega} X(\omega) P(\omega) + \sum_{\omega} Y(\omega) P(\omega) = E[X] + E[Y]$, by splitting one sum into two. Likewise $E[cX] = \sum_{\omega} c\,X(\omega) P(\omega) = c \sum_{\omega} X(\omega) P(\omega) = c\,E[X]$. $\blacksquare$

Proof. Write $X$ as the sum of its indicators and apply linearity $n - 1$ times, $E[X] = E[X_1] + \cdots + E[X_n] = p + \cdots + p = np$. $\blacksquare$

The proof never touched the binomial probabilities, which is the strength of linearity. It justifies the previous chapter's error counts, such as 28.8 errors in an hour of $2.88 \times 10^{13}$ bits on a link with $p = 10^{-12}$, even though the count in any given hour could be anything from zero upward.

Spread

The mean says nothing about how far a count strays from it. For the three bits, the squared distances of the four possible counts from the mean 0.3 are $(0 - 0.3)^2 = 0.09$, $(1 - 0.3)^2 = 0.49$, $(2 - 0.3)^2 = 2.89$ and $(3 - 0.3)^2 = 7.29$. Weighting them by their probabilities gives $0.09 \times 0.729 + 0.49 \times 0.243 + 2.89 \times 0.027 + 7.29 \times 0.001 = 0.27$. Squaring keeps distances above and below the mean from canceling.

For the three bits, $\sigma = \sqrt{0.27} = 0.5196$ flips. A second formula for the variance is usually quicker.

Proof. Expand the square and apply linearity, treating $\mu$ as a constant, $E\bigl[(X - \mu)^2\bigr] = E[X^2] - 2\mu\,E[X] + \mu^2 = E[X^2] - 2\mu^2 + \mu^2 = E[X^2] - \mu^2$. For the second claim, $cX$ has mean $c\mu$, so $\operatorname{Var}(cX) = E\bigl[(cX - c\mu)^2\bigr] = c^2 E\bigl[(X - \mu)^2\bigr]$. $\blacksquare$

The check is $E[X^2] = 1 \times 0.243 + 4 \times 0.027 + 9 \times 0.001 = 0.36$, and $0.36 - 0.3^2 = 0.27$. Means add for any random variables, but variances add only for independent ones. Random variables $X$ and $Y$ are independent when $P(X = x \text{ and } Y = y) = P(X = x) \, P(Y = y)$ for every pair of values $x$ and $y$, as the indicators of different bits on a binary symmetric channel are.

Proof. Group the outcomes by the pair of values $(x, y)$. Then $E[XY] = \sum_x \sum_y x y \, P(X = x \text{ and } Y = y) = \sum_x \sum_y x y \, P(X = x) P(Y = y)$, and the double sum factors as $\bigl(\sum_x x\,P(X = x)\bigr)\bigl(\sum_y y\,P(Y = y)\bigr) = E[X]\,E[Y]$. $\blacksquare$

Proof. Write $\mu_X$ and $\mu_Y$ for the two means. By the lemma on the second moment and linearity,

$$\operatorname{Var}(X+Y) = E[X^2] + 2E[XY] + E[Y^2] - \mu_X^2 - 2\mu_X\mu_Y - \mu_Y^2 = \operatorname{Var}(X) + \operatorname{Var}(Y) + 2\bigl(E[XY] - \mu_X\mu_Y\bigr).$$

The last bracket is zero by the product lemma. For $n$ variables, add them one at a time. Under mutual independence the partial sum $X_1 + \cdots + X_k$ is independent of $X_{k+1}$, so each new term adds its own variance. $\blacksquare$

Proof. An indicator takes only the values 0 and 1, so $X_i^2 = X_i$ and $E[X_i^2] = p$. The lemma gives $\operatorname{Var}(X_i) = p - p^2 = p(1-p)$. The indicators are mutually independent, so their variances add to $np(1-p)$. $\blacksquare$

For three bits, $3 \times 0.1 \times 0.9 = 0.27$, matching the direct sum. For the fast link, Table 2 sets each mean beside its standard deviation.

The last column falls as the span grows. The standard deviation is close to $\sqrt{Np}$, since $1 - p$ is all but 1, so it grows as the square root of the number of bits while the mean grows in proportion, and their ratio shrinks like $1/\sqrt{Np}$, from about a third of the mean for a terabyte to under 4% for a day.

04.The Law of Large Numbers

A test bench measures a bit error rate by dividing the errors found by the bits sent. Whether that fraction approaches the true $p$, and how many bits it needs, depends on turning a mean and a variance into a statement about probability, which the next two inequalities do.

Markov's Inequality

Take a frame of 1000 bits on a channel with $p = 0.01$, so the mean number of errors is $1000 \times 0.01 = 10$. Suppose nothing else is known except that the count is never negative. If more than half of all frames carried 20 or more errors, those frames alone would push the average above $\tfrac{1}{2} \times 20 = 10$. So at most half do.

Proof. Split the defining sum of $E[X]$ into the values below $a$ and the values at or above it. The first part is at least zero, because $X \ge 0$, and in the second each value is at least $a$, so

$$E[X] = \sum_k k\,P(X = k) \ \ge\ \sum_{k \ge a} k\,P(X = k) \ \ge\ a \sum_{k \ge a} P(X = k) = a\,P(X \ge a).$$

Dividing by $a$ gives the theorem. $\blacksquare$

The frame example gives $P(X \ge 20) \le 10/20 = 0.5$, more than a hundred times the exact binomial value 0.0032884, because the inequality uses nothing but the mean. The proof has a picture. The step that is 1 for $x \ge a$ and 0 below never exceeds the line $x/a$ when $x \ge 0$, and averaging both sides over the distribution of $X$ is the proof. Figure 4 draws the step with three curves above it, and the closer a curve hugs the step where the probability sits, the better its bound.

Chebyshev's Inequality

The variance adds information that the mean lacks, and applying Markov's inequality to the squared distance from the mean puts it to work.

Proof. The random variable $Y = (X - \mu)^2$ is never negative and has mean $\sigma^2$. The event $|X - \mu| \ge d$ is the same as $Y \ge d^2$, so Markov's inequality applied to $Y$ with $a = d^2$ gives $P(|X - \mu| \ge d) = P(Y \ge d^2) \le \sigma^2 / d^2$. $\blacksquare$

For the frame, the variance is $1000 \times 0.01 \times 0.99 = 9.9$. Twenty or more errors means a distance of at least 10 above the mean, so $P(X \ge 20) \le P(|X - 10| \ge 10) \le 9.9/100 = 0.099$. That is five times better than Markov and still about thirty times the exact 0.0032884.

The real use of Chebyshev's inequality is that it holds for every distribution with that mean and variance. Setting $d = k\sigma$ shows that no random variable lands $k$ or more standard deviations from its mean with probability above $1/k^2$. For a day on the fast link, four standard deviations are $4 \times 26.29 = 105.2$ errors, so the day's count lies between $691.2 - 105.2 = 586.0$ and $691.2 + 105.2 = 796.4$ except with probability at most $1/16 = 0.0625$, and a count outside that range is strong evidence that the error rate is not $10^{-12}$.

Averages Settle Down

Proof. By linearity, $E[\bar{X}_n] = \tfrac{1}{n}(n\mu) = \mu$. By the variance of a sum and the rule $\operatorname{Var}(cX) = c^2 \operatorname{Var}(X)$, $\operatorname{Var}(\bar{X}_n) = \tfrac{1}{n^2}(n\sigma^2) = \sigma^2/n$. Chebyshev's inequality with $d = \varepsilon$ gives the bound. $\blacksquare$

Here $\varepsilon$, the Greek letter epsilon, is the tolerance. However small it is, a long enough run makes a miss as unlikely as desired. In Figure 5, three simulated runs of a channel with $p = 0.1$ wander over their first few dozen bits and then settle, and by 10,000 bits each sits inside a band of half-width $2\sqrt{p(1-p)/n} = 0.006$ around the true value.

For a bit error rate measurement, let $X_i$ be the indicator that bit $i$ arrived wrong, so $\mu = p$ and $\sigma^2 = p(1-p)$, and $\bar{X}_n$ is the measured error fraction. Asking for the measurement to land within $\varepsilon$ of $p$ except with probability $\delta$, the Greek letter delta, means making the right side of Equation 9 at most $\delta$, which needs

$$n \ge \frac{p(1-p)}{\varepsilon^2 \delta}.$$

To measure $p = 10^{-3}$ to within $\varepsilon = 10^{-4}$ with failure probability $\delta = 0.05$, Chebyshev asks for $n \ge 0.000999 / (10^{-8} \times 0.05) = 1{,}998{,}000$ bits. The demand is generous, because it holds for any distribution. At $n = 10^6$ bits the standard deviation of the measured fraction is already $\sqrt{p(1-p)/n} = 3.16 \times 10^{-5}$, so the tolerance sits more than three standard deviations away. Sharper statements need the shape of the distribution.

05.The Gaussian and the Q-Function

Underneath a bit flip there is usually a voltage. Suppose a transmitter sends a 1 as $+1$ volt and a 0 as $-1$ volt, and the wire adds a random noise voltage with mean 0 and standard deviation $\sigma = 0.5$ volt. The receiver decides 1 when the voltage it sees is above 0 and 0 otherwise. When a 1 is sent, the decision is wrong if the noise falls below $-1$ volt, more than two standard deviations below its mean. For the noise found in practice that happens with probability $Q(2) = 0.02275$, the shaded area in Figure 6.

Densities

A voltage takes values in a continuous range, so any one exact value has probability zero. Probabilities come instead from a density, a curve $f(x) \ge 0$ with total area 1, and the probability of landing between $a$ and $b$ is the area under the curve between them, written $\int_a^b f(x)\,dx$. The symbol $\int$, an elongated S for "sum," stands for the limit of adding many thin rectangles of width $dx$ and height $f(x)$. Every earlier rule carries over with sums replaced by areas, so $E[X] = \int x f(x)\,dx$, $\operatorname{Var}(X) = \int (x - \mu)^2 f(x)\,dx$, and linearity holds as before.

The standard curve peaks at $\phi(0) = 1/\sqrt{2\pi} = 0.3989$ and falls off symmetrically, faster than any power of $x$. The received voltage for a sent 1 in the opening example is $N(1, 0.25)$, a copy of the standard curve half as wide and twice as tall.

Proof. Let $I = \int_{-\infty}^{\infty} e^{-x^2/2}\,dx$. Its square is a volume over the whole plane, $I^2 = \int\!\!\int e^{-(x^2 + y^2)/2}\,dx\,dy$, and the trick is to compute that volume in rings. The height $e^{-(x^2+y^2)/2}$ depends only on the distance $r = \sqrt{x^2 + y^2}$ from the origin. The thin ring between radius $r$ and $r + dr$ has circumference $2\pi r$, width $dr$ and therefore area $2\pi r\,dr$, so

$$I^2 = \int_0^\infty e^{-r^2/2}\, 2\pi r\,dr = 2\pi \Bigl[-e^{-r^2/2}\Bigr]_0^\infty = 2\pi(0 + 1) = 2\pi,$$

where the bracket evaluates an antiderivative at the two ends, checked by differentiating $-e^{-r^2/2}$ to get $r e^{-r^2/2}$. So $I = \sqrt{2\pi}$, and dividing by $\sqrt{2\pi}$ makes the total area of $\phi$ equal to 1. The mean $\int x\,\phi(x)\,dx$ is 0, because $\phi(-x) = \phi(x)$ and the contributions of $x$ and $-x$ cancel. For the variance, note that differentiating gives $\phi'(x) = -x\,\phi(x)$. Integration by parts, which is the product rule for derivatives read backward, $\int u\,v'\,dx = [uv] - \int u'\,v\,dx$, with $u = x$ and $v = -\phi$, gives

$$\int_{-\infty}^{\infty} x^2 \phi(x)\,dx = \int_{-\infty}^{\infty} x \cdot x\phi(x)\,dx = \Bigl[-x\,\phi(x)\Bigr]_{-\infty}^{\infty} + \int_{-\infty}^{\infty} \phi(x)\,dx = 0 + 1 = 1,$$

since $x\,\phi(x)$ vanishes at both ends. $\blacksquare$

Every Gaussian is a stretched and shifted standard one. If $Z$ is standard, then $X = \mu + \sigma Z$ has mean $\mu$ and variance $\sigma^2$ by linearity and the scaling rule, and substituting $x = \mu + \sigma z$ in the area $P(X \le t) = \int_{-\infty}^{(t - \mu)/\sigma} \phi(z)\,dz$ turns it into $\int_{-\infty}^{t} \tfrac{1}{\sigma}\phi\bigl((x - \mu)/\sigma\bigr)\,dx$, whose integrand is exactly Equation 10. So a question about any Gaussian becomes a question about $Z$, by measuring distances from the mean in units of $\sigma$.

Thermal noise in a receiver is close to Gaussian because it is the sum of the tiny voltages of an enormous number of electrons moving independently. The central limit theorem says that for mutually independent terms with a common distribution of mean $\mu$ and variance $\sigma^2$, the probabilities of $(X_1 + \cdots + X_n - n\mu)/(\sigma\sqrt{n})$ approach those of $Z$ as $n$ grows, whatever that distribution is. Its proof needs tools beyond this chapter and is given by Grinstead and Snell [1]. The theorem also makes a binomial count with large $n$ look roughly Gaussian, with limits that the warning at the end of this section examines.

The Q-Function

For a Gaussian $X$ with mean $\mu$ and standard deviation $\sigma$, $P(X > \mu + x\sigma) = Q(x)$, and by the symmetry of $\phi$ the lower tail is the same, $P(X < \mu - x\sigma) = Q(x)$. In the opening example the noise must fall $1/0.5 = 2$ standard deviations below its mean, so the error probability is $Q(2) = 0.02275$. Table 3 shows the error probability collapsing as the noise shrinks.

Halving the noise from 0.5 to 0.25 volt cuts the error probability by a factor of $Q(2)/Q(4) = 718$. The same steep curve returns whenever coded and uncoded systems are compared later in the book.

The Q-function is not on a calculator's keyboard, so on paper it is bounded, and the bounds below are tight exactly where coding needs them, far out in the tail.

Proof. The upper bound uses $t/x > 1$ for $t > x$, so $Q(x) = \int_x^\infty \phi(t)\,dt < \int_x^\infty \tfrac{t}{x}\phi(t)\,dt$. Since $-\phi$ has derivative $t\,\phi(t)$, the last integral is $\tfrac{1}{x}\bigl[-\phi(t)\bigr]_x^\infty = \phi(x)/x$.

The lower bound starts from the derivative of $\phi(t)/t$, which is $\bigl(t\,\phi'(t) - \phi(t)\bigr)/t^2 = -\phi(t)\bigl(1 + 1/t^2\bigr)$. Integrating from $x$ to infinity gives $\int_x^\infty \bigl(1 + 1/t^2\bigr)\phi(t)\,dt = \phi(x)/x$. For $t > x$ the factor $1 + 1/t^2$ is less than $1 + 1/x^2$, so $\phi(x)/x < \bigl(1 + 1/x^2\bigr) Q(x)$, which rearranges to $Q(x) > x\,\phi(x)/(1 + x^2)$.

For the last bound, substitute $t = x + u$, so that $Q(x) = \int_0^\infty \phi(x + u)\,du$. Expanding the square in the exponent, $\phi(x + u) = \phi(u)\,e^{-x^2/2}\,e^{-xu}$, and $e^{-xu} \le 1$ for $u \ge 0$. Hence $Q(x) \le e^{-x^2/2}\int_0^\infty \phi(u)\,du = \tfrac{1}{2}e^{-x^2/2}$, because half the area of $\phi$ lies to the right of 0. $\blacksquare$

Table 4 and Figure 7 show the squeeze. At $x = 6$ the upper bound is only 1.026 times $Q$, and $Q$ only 1.0013 times the lower bound. The simpler bound $\tfrac{1}{2}e^{-x^2/2}$ is looser by a growing factor, but it shows the essential fall like $e^{-x^2/2}$ with the easiest algebra to carry through a calculation.

06.The Union Bound

The decoder for $R_3$ fails when some pair of bits both flip, which is the union of three events, "bits 1 and 2 flipped," "bits 1 and 3 flipped" and "bits 2 and 3 flipped." Each has probability $p^2 = 0.01$, so adding them gives $3p^2 = 0.03$, against the exact 0.028. As Figure 8 shows, the sum counts the pattern 111 three times where the union counts it once, an excess of $2 \times 0.001 = 0.002$. Adding the probabilities of overlapping events can only overcount.

Proof. For two events, inclusion–exclusion gives $P(A_1 \cup A_2) = P(A_1) + P(A_2) - P(A_1 \cap A_2) \le P(A_1) + P(A_2)$, since no probability is negative. Suppose the bound holds for $m - 1$ events. Writing the union of $m$ events as the union of two, $U = A_1 \cup \cdots \cup A_{m-1}$ and $A_m$, the two-event case gives $P(U \cup A_m) \le P(U) + P(A_m)$, and the assumption bounds $P(U)$ by the sum of the first $m - 1$ probabilities. By induction the bound holds for every $m$. $\blacksquare$

Proof. At least $t$ flips occur exactly when some set of $t$ positions all flip. For each of the $\binom{n}{t}$ sets $S$ of $t$ positions, the event "every bit in $S$ flipped" has probability $p^t$ by mutual independence, whatever the other bits do. The union bound over all the sets gives the theorem. $\blacksquare$

The bound is excellent when errors are rare, because the overcount comes from outcomes lying in two events at once, which are rarer still. Server memory protects each 64-bit word with an 8-bit check, a 72-bit code that corrects one error and detects two [2]. If each stored bit is upset with probability $q = 10^{-6}$ between checks, independently, the chance of any error is at most $72q = 7.2 \times 10^{-5}$, against an exact $7.19974 \times 10^{-5}$, and the chance of two or more, beyond correction, is at most $\binom{72}{2} q^2 = 2.556 \times 10^{-9}$, against an exact $2.55588 \times 10^{-9}$. The same bound gives the leading term of the previous chapter's $R_5$ formula, since five copies fail with three or more flips, at most $\binom{5}{3}p^3 = 10^{-5}$ at $p = 0.01$ against an exact $9.8506 \times 10^{-6}$.

The bound is worthless when the events are common. For the previous chapter's server with 16 memory modules, each with an 8% chance of an error in a year, it gives $16 \times 0.08 = 1.28$, while the exact value under independence is $1 - 0.92^{16} = 0.7366$. The union bound is a tool for rare events, the regime every working code is designed for.

07.The Chernoff Bound

Table 5 puts the tools of this chapter side by side on two tail probabilities, the chance of at least twice the mean number of errors in 1000 bits and in 10,000 bits on a channel with $p = 0.01$.

Markov's bound does not improve with length at all, and Chebyshev's improves only in proportion to $n$. The exact tail falls by a factor of more than $10^{15}$ between the two columns, and only the Chernoff bound keeps pace, staying above the truth, as a bound must, by a factor of about 18 at $n = 10{,}000$. The Gaussian approximation lands below the truth. Figure 9 shows the same contrast across a range of thresholds for the 1000-bit frame.

The idea, due to Chernoff [3], is to apply Markov's inequality to $e^{sX}$ for a positive number $s$ chosen afterward, since an exponential separates a tail value from the mean far more sharply than a line or a parabola can. For numbers $a$ and $p$ strictly between 0 and 1, the resulting exponent is the relative entropy of $a$ from $p$, measured in natural logarithms,

$$D(a \,\|\, p) = a \ln\frac{a}{p} + (1 - a)\ln\frac{1-a}{1-p}.$$

Proof. For any $s > 0$ the function $e^{sx}$ is increasing, so the event $X \ge an$ is the same as $e^{sX} \ge e^{san}$. Markov's inequality applied to the positive random variable $e^{sX}$ gives $P(X \ge an) \le E[e^{sX}] / e^{san}$.

Write $X = X_1 + \cdots + X_n$ with indicators. Then $e^{sX} = e^{sX_1} \cdots e^{sX_n}$, a product of independent factors, so the product lemma, applied one factor at a time, gives $E[e^{sX}] = \prod_i E[e^{sX_i}]$. Each factor is $E[e^{sX_i}] = (1 - p)e^0 + p\,e^s = 1 - p + p e^s$. Therefore

$$P(X \ge an) \le \Bigl( \bigl(1 - p + p e^s\bigr) e^{-sa} \Bigr)^n \quad \text{for every } s > 0.$$

The best $s$ minimizes the logarithm of the bracket, $g(s) = \ln(1 - p + pe^s) - sa$. Setting its derivative $pe^s/(1 - p + pe^s) - a$ to zero and solving gives $e^s = a(1-p)/\bigl(p(1-a)\bigr)$, which exceeds 1 because $a > p$, so this $s$ is positive. With that choice, $1 - p + pe^s = (1 - p) + a(1-p)/(1-a) = (1-p)/(1-a)$, and the bracket becomes

$$\frac{1-p}{1-a} \left(\frac{p(1-a)}{a(1-p)}\right)^{a} = \left(\frac{p}{a}\right)^{a} \left(\frac{1-p}{1-a}\right)^{1-a} = e^{-D(a \| p)}.$$

Raising it to the power $n$ gives the theorem. $\blacksquare$

The bound has teeth because $D(a \,\|\, p) > 0$ whenever $a > p$. At $s = 0$ the function $g$ equals $\ln 1 = 0$ and has slope $p - a < 0$, so $g$ dips below zero for small positive $s$, and its minimum, $-D(a \,\|\, p)$, is negative. The probability that the fraction of flipped bits reaches $a$ therefore falls exponentially in $n$, at a rate set by how far $a$ is from $p$.

For the 1000-bit frame with $p = 0.01$ and the threshold $a = 0.02$, the optimal $e^s = 0.02 \times 0.99 / (0.01 \times 0.98) = 2.0204$, so $s = 0.7033$, and $(1 - p)/(1 - a) = 1.0102$. The exponent is $D(0.02 \,\|\, 0.01) = 0.02 \ln 2 + 0.98 \ln(0.98/0.99) = 0.0039136$, so $nD = 3.9136$ and the bound is $e^{-3.9136} = 0.0200$. That is five times better than Chebyshev at this length, and multiplying the length by ten raises the exponent to $39.136$ and the bound to $1.008 \times 10^{-17}$.

The Repetition Code, Again

The majority decoder of $R_n$, for odd $n$, fails when more than half the copies flip, which implies $X \ge n/2$. Setting $a = 1/2$ in the Chernoff bound gives an exponent that simplifies neatly,

$$D\bigl(\tfrac{1}{2} \,\big\|\, p\bigr) = \tfrac{1}{2}\ln\frac{1}{2p} + \tfrac{1}{2}\ln\frac{1}{2(1-p)} = -\tfrac{1}{2}\ln\bigl(4p(1-p)\bigr),$$

and so

$$P_e(R_n) \le e^{-n D(1/2 \| p)} = \bigl(4p(1-p)\bigr)^{n/2}.$$

That is the bound the previous chapter proved by a counting argument written for the occasion. At $p = 0.1$, $D(\tfrac{1}{2} \,\|\, 0.1) = -\ln(0.36)/2 = 0.5108$, and for $R_{25}$ the bound is $0.36^{12.5} = 2.843 \times 10^{-6}$, against an exact failure probability of $1.621 \times 10^{-7}$. It is about eighteen times too large but has the right exponential rate, and it took one line. The relative entropy returns in Information and Entropy, which builds it from first principles, and in Capacity and Shannon's Theorem.

08.Looking Ahead

This chapter treated a channel as a list of flip probabilities. The next chapter, Channels, Signals and Likelihoods, opens the channel up. The binary symmetric channel is joined by the binary erasure channel, in which a bit is either delivered correctly or visibly lost, and the Z-channel, in which only one direction of flip occurs, as when charge leaks out of a memory cell but never in. The voltage example becomes the additive white Gaussian noise channel with binary phase-shift keying, together with signal space, the matched filter and the proof that the receiver built from them makes the fewest errors possible. The signal-to-noise ratio, measured in coding as the energy per bit over the noise density, $E_b/N_0$, replaces the bare $\sigma$ of Table 3, and comparing hard decisions, which keep only the bit, with soft decisions, which keep the voltage, shows how much a threshold throws away.

Bayes' rule becomes the receiver's main tool. The probability of a received voltage given each possible bit is a likelihood, and the log-likelihood ratio packs everything the receiver knows about one bit into a single signed number. The warning about bursts becomes the Gilbert–Elliott channel, a two-state model that switches between a good state and a bad one, and the chapter closes with the fault models of memory, stuck-at faults, transient upsets and multi-bit upsets, which decide what a memory code must survive. Lin and Costello [4] treat this material at greater length.

09.Worked Examples

10.Exercises

References

1. [1]Grinstead, Charles M. and Snell, J. Laurie (2006). “Grinstead and Snell's Introduction to Probability.” The CHANCE Project. Version dated 4 July 2006 of the second edition published by the American Mathematical Society, free under the GNU Free Documentation License. https://math.dartmouth.edu/~prob/prob/prob.pdf
2. [2]Hsiao, M. Y. (1970). “A Class of Optimal Minimum Odd-weight-column SEC-DED Codes.” IBM Journal of Research and Development, 14(4), pp. 395–401. doi:10.1147/rd.144.0395
3. [3]Chernoff, Herman (1952). “A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations.” The Annals of Mathematical Statistics, 23(4), pp. 493–507. doi:10.1214/aoms/1177729330
4. [4]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.