46.03.06 · information-theory / channel-capacity

Feedback Does Not Increase Capacity

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.12; Shannon 1956 The Zero Error Capacity of a Noisy Channel; Wolfowitz 1964 Coding Theorems of Information Theory; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §2.1-2.3

Intuition Beginner

Imagine you are sending messages through a noisy telegraph wire. You send a symbol, the wire corrupts it, and the receiver gets something slightly different. Now suppose the receiver can send you a signal back, telling you what they actually received. Does this help you send more information per use of the wire?

The surprising answer is: no, not for the basic channel model. Even with perfect, instantaneous feedback telling you exactly what the receiver got, you cannot squeeze more bits through the channel than you could without it. The capacity is the same either way.

Why? Because the capacity already represents the best possible exploitation of the channel statistics. Feedback lets you adapt your future inputs based on past outputs, but the noise on each new symbol is independent of everything that came before. The new noise is fresh, and feedback cannot predict it. You already knew the best input distribution for the channel; feedback does not give you a better one.

Feedback does help with other things. It simplifies coding (you can use much simpler error-correction schemes). It helps the encoder know when errors have occurred and resend selectively. But the maximum rate of reliable communication does not budge.

There is one important exception: if you care about zero-error communication, where the decoder must never make a single mistake, feedback can help. The zero-error capacity with feedback can exceed the zero-error capacity without feedback. But for the standard setup, where a vanishingly small error rate is allowed, the answer is firm: feedback does not increase capacity.

Visual Beginner

Figure: a schematic of a discrete memoryless channel with and without feedback. Left: the standard setup, where the input $X_{i}$ depends only on the message $W$ . Right: the feedback setup, where the input $X_{i}$ depends on the message $W$ and all previous channel outputs $Y_{1}, \dots, Y_{i - 1}$ via a dashed return arrow from receiver to transmitter.

Property	Without feedback	With feedback
Capacity	$C = max_{p (x)} I (X; Y)$	$C_{F B} = C$ (same)
Coding complexity	High (large random codebooks)	Lower (simpler schemes suffice)
Error exponent	Standard random coding exponent	Can improve for moderate blocklengths
Zero-error capacity	$C_{0}$	$C_{0, F B} \geq C_{0}$ (can be strictly larger)

The capacity number is the same, but the path to achieving it is easier with feedback.

Worked example Beginner

Consider a binary symmetric channel with crossover probability $p = 0.1$ . The capacity is $C = 1 - H (0.1) \approx 1 - 0.469 = 0.531$ bits per channel use.

Without feedback: you must use a fixed codebook. You pick your $2^{n R}$ codewords ahead of time, send them, and the decoder figures out which one was most likely transmitted. For rates below 0.531 bits/use, you can drive the error probability to zero by using long enough codewords.

With feedback: the transmitter gets to see what the receiver observed at each step. Can the transmitter adapt and push the rate above 0.531? No. Even with perfect feedback, the maximum rate is still 0.531 bits per use. The noise on each new symbol is an independent coin flip with 10 percent error probability, and knowing past outcomes does not change the statistics of the next one.

What feedback does help with: instead of using a huge random codebook, the transmitter can use a simple scheme. Send the message bits directly. If the receiver reports an error (via feedback), resend just that bit. The average rate is still bounded by 0.531, but the encoding and decoding are much simpler.

Check your understanding Beginner

Formal definition Intermediate+

Let $p (y ∣ x)$ be a discrete memoryless channel (DMC) with input alphabet $X$ and output alphabet $Y$ .

Definition (Feedback code). A $(2^{n R}, n)$ feedback code for the DMC consists of:

A message set $W = {1, 2, \dots, 2^{n R}}$ .
A sequence of encoding functions $x_{i} = f_{i} (W, Y_{1}, \dots, Y_{i - 1})$ for $i = 1, \dots, n$ , where $W \in W$ is the message and $Y_{1}, \dots, Y_{i - 1}$ are the previously received channel outputs.
A decoding function $\hat{W} = g (Y_{1}, \dots, Y_{n})$ mapping the received sequence to a message estimate.

The channel acts as $Y_{i} \sim p (y_{i} ∣ x_{i})$ conditionally independently given $x_{i}$ . The key difference from a standard code is that each input symbol $X_{i}$ can depend on all past outputs $Y^{i - 1} = (Y_{1}, \dots, Y_{i - 1})$ .

Definition (Capacity with feedback). The capacity with feedback $C_{F B}$ is the supremum of all rates $R$ such that there exists a sequence of $(2^{n R}, n)$ feedback codes with probability of error $P_{e}^{(n)} = Pr [\hat{W} \neq = W] \to 0$ as $n \to \infty$ .

Theorem (Shannon 1956). For any discrete memoryless channel,

C_{F B} = C = p (x) max I (X; Y) .

Key theorem with proof Intermediate+

Theorem (Feedback does not increase capacity). Let $C_{F B}$ denote the capacity of a DMC with noiseless feedback. Then $C_{F B} = C$ , where $C = max_{p (x)} I (X; Y)$ is the capacity without feedback.

Proof (converse). We show that even with feedback, $I (X^{n}; Y^{n}) \leq n C$ for any encoding scheme where $X_{i} = f_{i} (W, Y^{i - 1})$ .

By the chain rule for mutual information:

I (X^{n}; Y^{n}) = i = 1 \sum n I (X^{n}; Y_{i} ∣ Y^{i - 1}) .

For each term, we have:

I (X^{n}; Y_{i} ∣ Y^{i - 1}) = H (Y_{i} ∣ Y^{i - 1}) - H (Y_{i} ∣ X^{n}, Y^{i - 1}) .

Since the channel is memoryless, $Y_{i}$ depends only on $X_{i}$ (not on other inputs or past outputs) given $X_{i}$ . Therefore $H (Y_{i} ∣ X^{n}, Y^{i - 1}) = H (Y_{i} ∣ X_{i})$ , because once $X_{i}$ is known, the rest of $X^{n}$ and $Y^{i - 1}$ provide no additional information about $Y_{i}$ .

Also, $H (Y_{i} ∣ Y^{i - 1}) \leq H (Y_{i})$ (conditioning reduces entropy). So:

I (X^{n}; Y_{i} ∣ Y^{i - 1}) \leq H (Y_{i}) - H (Y_{i} ∣ X_{i}) = I (X_{i}; Y_{i}) .

Each term is bounded by the single-letter mutual information $I (X_{i}; Y_{i}) \leq C$ . Summing over $i = 1, \dots, n$ :

I (X^{n}; Y^{n}) \leq i = 1 \sum n I (X_{i}; Y_{i}) \leq n C .

By Fano's inequality (as in the standard converse), $n R \leq I (X^{n}; Y^{n}) + n ϵ_{n} \leq n C + n ϵ_{n}$ , giving $R \leq C + ϵ_{n} \to C$ . Since $C_{F B} \geq C$ (feedback codes include non-feedback codes as a special case), we conclude $C_{F B} = C$ . $□$

Bridge. The feedback converse builds toward the network information theory units 46.06.01-46.06.04 by establishing the baseline fact that single-user capacity is unchanged by feedback; this is exactly the starting assumption that makes multi-user feedback results so surprising, because feedback can enlarge the capacity region for multiple-access 46.06.01 and relay 46.06.03 channels. The conditional-mutual-information bound $I (X^{n}; Y_{i} ∣ Y^{i - 1}) \leq I (X_{i}; Y_{i})$ is the foundational reason why memorylessness kills the feedback advantage: past outputs are irrelevant to the current noise realization. The result appears again in 46.05.03 as a foil: Gelfand-Pinsker coding shows that knowing the future channel state (not past outputs) at the transmitter generalises the feedback picture and does change the achievable rate. Putting these together, feedback helps with coding complexity and error exponents but the central insight is that the capacity number itself is invariant.

Exercises Intermediate+

Exercise (hard, short answer).

Prove that feedback does not increase the capacity of a state-dependent channel $p (y ∣ x, s) p (s)$ when the channel state is unknown to both transmitter and receiver (i.e., the state is averaged out).

Hint

The averaged channel $\overset{p}{ˉ} (y ∣ x) = \sum_{s} p (s) p (y ∣ x, s)$ is still memoryless. Apply the standard feedback converse to this averaged channel.

Answer

When the state $S$ is unknown to both parties and i.i.d. across time, the effective channel from the transmitter's perspective is the averaged channel $\overset{p}{ˉ} (y ∣ x) = \sum_{s} p (s) p (y ∣ x, s)$ , which is memoryless. The feedback converse applies directly to this averaged channel: the capacity with feedback equals $max_{p (x)} I_{\overset{p}{ˉ}} (X; Y)$ , which is the same as the capacity without feedback. The state being hidden from both parties means it simply modifies the transition probabilities but does not break the memorylessness argument.

Exercise (hard, short answer).

Consider a channel where the noise $Z_{i}$ is not independent across time but instead $Z_{i} = Z_{i - 1}$ for all $i$ (constant but unknown noise). Show that feedback can increase capacity for this channel.

Hint

With feedback, the transmitter can learn the noise value from the first channel output and compensate perfectly thereafter.

Answer

Without feedback, the noise $Z$ is a single unknown value (constant across time), and the transmitter must code against all possible noise realizations. With feedback, the transmitter sends $X_{1}$ , observes $Y_{1} = X_{1} + Z$ (for an additive channel), and deduces $Z = Y_{1} - X_{1}$ . For all subsequent symbols $i \geq 2$ , the transmitter sets $X_{i} = W_{i} - Z$ where $W_{i}$ is the intended message symbol, yielding $Y_{i} = W_{i}$ noiselessly. The effective rate approaches 1 symbol per use (minus the one-symbol overhead), which exceeds the non-feedback capacity. The channel is not memoryless, so the Shannon 1956 result does not apply.

Exercise (hard, short answer).

Prove that the reliability function (error exponent) of the DMC with feedback equals the reliability function without feedback at rates below critical rate. Why does the error exponent match despite feedback simplifying the code construction?

Hint

The random coding exponent is tight below critical rate (Sphere-packing bound). Feedback cannot improve what is already optimal.

Answer

Below the critical rate $R_{cr}$ , the random coding exponent $E_{r} (R)$ equals the sphere-packing exponent $E_{s p} (R)$ , which is a tight lower bound on the error exponent for any code (with or without feedback). Since feedback codes are a superset of non-feedback codes, the best possible error exponent with feedback is at least $E_{r} (R)$ . But the sphere-packing converse shows no code can exceed $E_{s p} (R) = E_{r} (R)$ below critical rate. Hence the exponent is the same. At rates above $R_{cr}$ , feedback can potentially improve the error exponent, but the capacity boundary itself is unchanged.

Lean formalization Intermediate+

Mathlib does not define feedback codes, capacity with feedback, or the converse theorem that $C_{F B} = C$ for the DMC. The probabilistic objects needed — adapted stochastic processes where $X_{i}$ is measurable with respect to $σ (W, Y^{i - 1})$ — exist in Mathlib's filtration and adapted-process framework (MeasureTheory.Filtration, MeasureTheory.Adapted), but they have not been connected to channel coding. The chain-rule decomposition of mutual information under the memoryless constraint, and the key step $H (Y_{i} ∣ X^{n}, Y^{i - 1}) = H (Y_{i} ∣ X_{i})$ , would require a formalized DMC structure and conditional-independence lemmas. This unit ships without formalization.

Advanced results Master

The Schalkwijk-Kailath scheme

Although feedback does not increase capacity, it dramatically simplifies code construction. The Schalkwijk-Kailath scheme (1966) provides an explicit, deterministic feedback coding strategy for the additive white Gaussian noise channel that achieves capacity with a remarkably simple structure:

Encode the message as a scalar $θ \in [0, 1)$ .
At time $i$ , transmit $X_{i} = α_{i} (θ - \hat{θ}_{i - 1})$ , where $\hat{θ}_{i - 1}$ is the receiver's estimate of $θ$ based on $Y^{i - 1}$ .
The receiver updates $\hat{θ}_{i} = \hat{θ}_{i - 1} + β_{i} Y_{i}$ using the MMSE coefficient $β_{i}$ .

The error $θ - \hat{θ}_{n}$ decays doubly exponentially in $n$ for the noiseless-feedback case, far faster than the exponential decay of random coding. This demonstrates that while the rate is unchanged, the coding complexity and error performance at finite blocklengths can be dramatically improved.

Feedback and the error exponent

The reliability function $E (R)$ of the DMC is the largest exponent $E$ such that $P_{e} \leq exp (- n E (R))$ is achievable at rate $R$ . For rates below the critical rate $R_{cr}$ , feedback does not improve the error exponent because the random coding exponent $E_{r} (R)$ already equals the sphere-packing upper bound $E_{s p} (R)$ .

At rates above the critical rate but below capacity, the situation is more nuanced. Burnashev (1976) showed that the error exponent with feedback is $E_{F B} (R) = C_{1} (1 - R / C)$ , where $C_{1} = max_{x, x^{'}} D (p (\cdot ∣ x) ∥ p (\cdot ∣ x^{'}))$ is the maximum KL divergence between output distributions induced by different inputs. This is strictly larger than the non-feedback exponent for high rates, establishing that feedback improves the speed of convergence to vanishing error probability (though not the limiting rate).

Zero-error capacity and feedback

The zero-error capacity $C_{0}$ is the maximum rate at which communication is possible with probability of error exactly zero. Unlike the vanishing-error capacity $C$ , the zero-error capacity can strictly increase with feedback. Shannon (1956) showed that $C_{0, F B} \geq C_{0}$ , and for some channels the inequality is strict.

The confusability graph of a channel has vertices $X$ and edges between $x, x^{'}$ whenever $p (y ∣ x) > 0$ and $p (y ∣ x^{'}) > 0$ for some $y$ . The zero-error capacity without feedback equals the Shannon capacity of this graph, a combinatorial quantity. With feedback, the transmitter can avoid confusion sets adaptively, potentially achieving a higher rate.

Feedback for channels with memory

The Shannon 1956 result applies specifically to memoryless channels. For channels with memory (Gilbert-Elliott channels, finite-state channels, intersymbol interference channels), feedback can increase capacity. The reason is precisely the failure of the memorylessness argument: when the channel state persists across time, feedback reveals information about the current state that is useful for predicting future noise.

For a finite-state Markov channel where the state $S_{i}$ evolves as a Markov chain and the output satisfies $Y_{i} \sim p (y_{i} ∣ x_{i}, s_{i})$ , feedback provides observations that carry information about $S_{i}$ , which in turn predicts $S_{i + 1}$ . The transmitter can then adapt $X_{i + 1}$ based on its estimate of $S_{i + 1}$ , increasing the achievable rate above the non-feedback capacity.

Synthesis. The feedback-does-not-increase-capacity theorem is one of the most counterintuitive results in information theory: perfect knowledge of past outputs provides no rate advantage on a memoryless channel. The central insight is that the memoryless property makes past outputs irrelevant to the current noise realization, so the conditional mutual information bound $I (X^{n}; Y^{n}) \leq n C$ holds regardless of the feedback encoding strategy. The result generalises to show that any causal adaptation based on past observations cannot exceed the single-letter mutual information maximum. This is exactly the baseline against which multi-user results are measured: feedback can enlarge the capacity region of the multiple-access channel 46.06.01 and provides gains in channels with memory, but the single-user DMC result stands as the reference point. The Schalkwijk-Kailath scheme and Burnashev's error exponent analysis show that while the rate is invariant, feedback provides substantial engineering advantages in coding complexity and convergence speed.

Full proof set Master

Proposition (Mutual information bound under feedback). For any feedback encoding $X_{i} = f_{i} (W, Y^{i - 1})$ on a DMC $p (y ∣ x)$ :

I (W; Y^{n}) \leq I (X^{n}; Y^{n}) \leq n C .

Proof. Since $W \to X^{n} \to Y^{n}$ forms a Markov chain (the message determines the encoding strategy, which produces the inputs, which produce the outputs via the channel), the data-processing inequality gives $I (W; Y^{n}) \leq I (X^{n}; Y^{n})$ .

For the second inequality, decompose:

I (X^{n}; Y^{n}) = i = 1 \sum n I (X^{n}; Y_{i} ∣ Y^{i - 1}) .

Each term satisfies:

I (X^{n}; Y_{i} ∣ Y^{i - 1}) = H (Y_{i} ∣ Y^{i - 1}) - H (Y_{i} ∣ X^{n}, Y^{i - 1}) .

By the memoryless property of the channel, $Y_{i}$ is independent of $(X^{i - 1}, X_{i + 1}^{n}, Y^{i - 1})$ given $X_{i}$ . Therefore $H (Y_{i} ∣ X^{n}, Y^{i - 1}) = H (Y_{i} ∣ X_{i})$ .

Since conditioning reduces entropy, $H (Y_{i} ∣ Y^{i - 1}) \leq H (Y_{i})$ . Hence:

I (X^{n}; Y_{i} ∣ Y^{i - 1}) \leq H (Y_{i}) - H (Y_{i} ∣ X_{i}) = I (X_{i}; Y_{i}) \leq C,

where the last inequality follows from the definition of capacity as the maximum of $I (X; Y)$ over input distributions. Summing over $i$ gives $I (X^{n}; Y^{n}) \leq n C$ . $□$

Proposition (Achievability with feedback). Since any non-feedback code is a valid feedback code (the encoding functions simply ignore $Y^{i - 1}$ ), the achievability of rate $C$ without feedback implies achievability with feedback. Combined with the converse, $C_{F B} = C$ .

Proof. Let ${C_{n}}$ be a sequence of $(2^{n R}, n)$ codes without feedback achieving rate $R < C$ with $P_{e}^{(n)} \to 0$ . Each such code has encoding functions $x_{i} = f_{i} (W)$ (independent of past outputs). These are valid feedback encoding functions (they simply do not use the feedback). Therefore $C_{F B} \geq C$ . Combined with $C_{F B} \leq C$ from the converse, $C_{F B} = C$ . $□$

Connections Master

46.03.02 — The achievability of capacity via random coding is the foundation; feedback codes include non-feedback codes, so achievability is inherited directly from the standard noisy-channel coding theorem.
46.03.03 — The converse proof uses Fano's inequality and the same rate-bounding argument as the non-feedback converse, with the additional step of bounding conditional mutual information under the memoryless constraint.
46.06.01 — The multiple-access channel has a feedback variant where feedback can enlarge the capacity region, creating a sharp contrast with the single-user result proved here.
46.06.03 — The relay channel uses feedback-like cooperation; the decode-and-forward and compress-and-forward strategies are analyzed against the baseline that single-user feedback provides no gain.
46.05.03 — Gelfand-Pinsker coding studies non-causal side information at the transmitter (knowing the channel state ahead of time), which contrasts with causal feedback and shows that the type of side information matters fundamentally.
46.03.05 — The Gaussian channel capacity with feedback is the same $C = \frac{1}{2} lo g (1 + SNR)$ ; the Schalkwijk-Kailath scheme achieves it with deterministic codes on the Gaussian channel.

Historical & philosophical context Master

Shannon established the feedback-capacity result in his 1956 paper "The Zero Error Capacity of a Noisy Channel" (Information and Control 1, 3-16). The paper's primary contribution was the zero-error capacity concept, but in the process Shannon observed that for the standard (vanishing-error) capacity, feedback provides no advantage. The proof is deceptively simple — a few lines of conditional mutual information manipulation — yet the result is deeply surprising to engineers who intuitively expect that more information at the transmitter should enable higher rates.

Jacob Wolfowitz strengthened the result in his 1964 book Coding Theorems of Information Theory (Springer, 2nd edition) by proving the strong converse under feedback: not only are rates above capacity unachievable, but the error probability is bounded away from zero uniformly over all feedback codes. This closed the gap between the weak converse (rates above capacity lead to non-vanishing error) and the strong converse.

The Schalkwijk-Kailath scheme appeared in "A Coding Scheme for Additive Noise Channels with Feedback" (IEEE Trans. Information Theory IT-12, 1966) and demonstrated that feedback, while not increasing capacity, can achieve capacity with explicit, deterministic codes rather than random ensembles. This was practically significant because random codes are exponentially large and cannot be stored.

Burnashev's 1976 result on the feedback error exponent ("Data Transmission Over a Discrete Channel with Feedback", Problems of Information Transmission 12(4)) established the exact reliability function with feedback, showing exponential improvement over the non-feedback case at high rates.

Bibliography Master

@article{shannon1956,
  author  = {Shannon, C. E.},
  title   = {The Zero Error Capacity of a Noisy Channel},
  journal = {Information and Control},
  volume  = {1},
  pages   = {3--16},
  year    = {1956},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@book{wolfowitz1964,
  author    = {Wolfowitz, J.},
  title     = {Coding Theorems of Information Theory},
  edition   = {2nd},
  publisher = {Springer},
  year      = {1964},
}
@article{schalkwijk-kailath1966,
  author  = {Schalkwijk, J. P. M. and Kailath, T.},
  title   = {A Coding Scheme for Additive Noise Channels with Feedback},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-12},
  pages   = {172--182},
  year    = {1966},
}
@article{burnashev1976,
  author  = {Burnashev, M. V.},
  title   = {Data Transmission Over a Discrete Channel with Feedback},
  journal = {Problems of Information Transmission},
  volume  = {12},
  number  = {4},
  pages   = {10--30},
  year    = {1976},
}
@book{csiszar-korner2011,
  author    = {Csisz{\'a}r, I. and K{\"o}rner, J.},
  title     = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
  edition   = {2nd},
  publisher = {Cambridge University Press},
  year      = {2011},
}

Prerequisites

46.03.02
46.03.03

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.12 (feedback as a channel resource, the surprising result that it does not increase capacity, and the physical picture)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.12 (formal definition of feedback codes, the converse proof that capacity is unchanged, and the role of conditioning)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §7.12; Shannon 1956 The Zero Error Capacity of a Noisy Channel; Wolfowitz 1964 Coding Theorems of Information Theory; Csiszar & Korner 2011 Information Theory: Coding Theorems for Discrete Memoryless Systems 2e (Cambridge) §2.1-2.3

References

Shannon, C. E. — The Zero Error Capacity of a Noisy Channel · Information and Control 1 (1956) 3-16; section on feedback in the discrete memoryless channel, establishing that feedback does not increase capacity for the DMC: even though the transmitter can adapt based on past outputs, the maximum rate of reliable communication remains $C = max_{p (x)} I (X; Y)$ .
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 7.12: definition of a DMC with feedback, the feedback coding scheme, and the proof that $C_{F B} = C = max_{p (x)} I (X; Y)$ for the discrete memoryless channel. The key insight is that past outputs $Y^{i - 1}$ are conditionally independent of the current input $X_{i}$ given $X^{i - 1}$ , so conditioning on feedback does not increase mutual information.
Wolfowitz, J. — Coding Theorems of Information Theory (2nd ed.) · Springer (1964). Chapter 5: the strong converse for the DMC with feedback, proving that rates above capacity are not achievable even with noiseless feedback. The result strengthens Shannon 1956 by establishing the strong converse under feedback.
Csiszar, I. & Korner, J. — Information Theory: Coding Theorems for Discrete Memoryless Systems (2nd ed.) · Cambridge University Press (2011). Section 2.1-2.3: the general framework for channel coding with and without feedback, showing that the capacity formula $C = max_{p (x)} I (X; Y)$ is invariant under the addition of noiseless feedback for the DMC.

Estimated time

beginner: 15m
intermediate: 45m
master: 90m