Back to the on-screen lesson ·
Transition matrices, output distributions, noise entropy, independence across uses.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to describe a discrete memoryless channel by its transition matrix, compute output distributions and noise entropies for a given input, explain what memorylessness means for blocks of uses, and recognise the binary symmetric, binary erasure and Z channels. You will define channel capacity as the maximum mutual information over input distributions, compute it for noiseless, useless and binary symmetric channels, explain why the uniform input is optimal when the noise entropy is fixed, and state the bounds that any capacity must satisfy, ready for the coding theorem that gives the definition its operational meaning.
A discrete memoryless channel (DMC) has a finite input alphabet $\mathcal{X}$, a finite output alphabet $\mathcal{Y}$, and a transition matrix $p(y \mid x)$ giving the probability of each output for each input; memoryless means each use is independent of the others, $p(y^n \mid x^n) = \prod_i p(y_i \mid x_i)$. Fixing an input distribution $p(x)$ makes $(X, Y)$ a joint distribution: the output law is $p(y) = \sum_x p(x) p(y \mid x)$ and the noise entropy is $H(Y \mid X) = \sum_x p(x) H(\text{row } x)$. The binary symmetric channel (BSC) flips a bit with probability $\varepsilon$; every row has entropy $h(\varepsilon)$. The binary erasure channel (BEC) replaces a bit by $?$ with probability $\alpha$ and never lies. The Z-channel corrupts only one of the two inputs. The mutual information $I(X; Y) = H(Y) - H(Y \mid X)$ measures, for a given input distribution, how many bits per use survive the noise; it is the quantity capacity will maximise.
Another way: picture
Two columns of dots, inputs on the left and outputs on the right, joined by arrows labelled with probabilities. The BSC has the crossed arrows labelled $\varepsilon$; the BEC has a third output $?$ that both inputs reach with probability $\alpha$.
Another way: steps
A discrete memoryless channel is three things: an input alphabet, an output alphabet and a transition matrix $p(y \mid x)$ whose row $x$ is the distribution of the output when $x$ is sent. Every row sums to $1$. Memoryless means each use is drawn from that matrix independently of the others, $p(y^n \mid x^n) = \prod_i p(y_i \mid x_i)$, so nothing carries over between uses — which is why the probability of $n$ clean uses is a product, and why a block of $n$ uses has capacity exactly $n$ times one use.
| channel | transition matrix (rows = inputs) | $H(Y \mid X)$ | row entropy |
|---|---|---|---|
| BSC($\varepsilon$) | $\begin{pmatrix} 1 - \varepsilon & \varepsilon \\ \varepsilon & 1 - \varepsilon \end{pmatrix}$ | $h(\varepsilon)$ | the same for both rows |
| BEC($\alpha$) | $\begin{pmatrix} 1 - \alpha & \alpha & 0 \\ 0 & \alpha & 1 - \alpha \end{pmatrix}$ | $h(\alpha)$ | the same for both rows |
| Z-channel | $\begin{pmatrix} 1 & 0 \\ 0.1 & 0.9 \end{pmatrix}$ | $q\, h(0.1)$ | row $0$ is certain, row $1$ is not |
| noiseless, $m$ inputs | the identity | $0$ | every row is certain |
Two quantities come straight from the matrix and the input distribution $p(x)$. The output law is total probability, $p(y) = \sum_x p(x)\, p(y \mid x)$: a column-weighted sum. The noise entropy is the average row entropy, $H(Y \mid X) = \sum_x p(x)\, H(\text{row } x)$. When every row has the same entropy — as in the BSC and the BEC — the noise entropy does not depend on the input at all, which is what makes their capacities so easy.
Common mistakes
Crossover $0.1$, $P(X = 1) = 0.3$: $P(Y = 1) = 0.3 \cdot 0.9 + 0.7 \cdot 0.1 = 0.34$.
Total probability.
$H(Y) = h(0.34) = 0.925$, $H(Y \mid X) = h(0.1) = 0.469$, so $I(X; Y) = 0.456$ bits: less than the $0.531$ of the uniform input.
The input distribution matters.
Input $0$ always arrives as $0$; input $1$ arrives as $1$ with probability $0.9$ and as $0$ with probability $0.1$.
Rows $(1, 0)$ and $(0.1, 0.9)$.
With $P(X = 1) = q$: $H(Y \mid X) = q \, h(0.1)$, not constant, so the best input is not uniform; the maximum of $I$ is at $q \approx 0.53$.
Asymmetric channels need a real maximisation.
BSC with crossover $\tfrac{1}{8}$ and $P(X = 1) = \tfrac{3}{8}$.
$P(Y = 1) = \tfrac{3}{8} \cdot \tfrac{7}{8} + \tfrac{5}{8} \cdot \tfrac{1}{8} = \tfrac{21 + 5}{64} = \tfrac{26}{64}$.
Sent as $1$ and not flipped, or sent as $0$ and flipped.
$= \tfrac{13}{32} = 0.40625$: the noise pulled the output toward $\tfrac{1}{2}$.
Erasure probability $\tfrac{1}{4}$, so each use survives with probability $\tfrac{3}{4}$.
Memorylessness makes the uses independent, so multiply.
$\left(\tfrac{3}{4}\right)^3 = \tfrac{27}{64}$, a little over $42\%$.
$P(Y = ?) = 0.2$ from either input.
Each row is $(0.8, 0.2)$ over $\{x, ?\}$: $H(Y \mid X) = h(0.2) = 0.722$ bits.
A binary symmetric channel flips its input with probability $2/8$. The input has $P(X = 1) = 7/8$. What is $P(Y = 1)$?
Computed value: answer
A binary symmetric channel has crossover probability $0.25$. Whatever the input distribution, what is $H(Y \mid X)$ in bits, to three decimal places?
Computed value: answer
A binary erasure channel erases each input with probability $1/4$, independently. What is the probability that $2$ consecutive uses suffer no erasure at all? Give a fraction.
Computed value: answer
A binary symmetric channel flips its input with probability $3/8$. The input has $P(X = 1) = 7/8$. What is $P(Y = 1)$?
Computed value: answer
What makes a channel a discrete memoryless channel?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A binary symmetric channel has crossover probability $0.15$. Whatever the input distribution, what is $H(Y \mid X)$ in bits, to three decimal places?
Computed value: answer
You can model a noisy channel and compute how much information one use can carry at best. Next: the two workhorse channels, binary symmetric and binary erasure, in detail.
9. Your turn: BEC with $\alpha = 0.2$ and $P(X = 1) = 0.5$; find $P(Y = ?)$ and $H(Y \mid X)$, step 2