Feedback Does Not Increase the Capacity of Approximately Memoryless Surjective POST Channels

This paper demonstrates that for approximately memoryless surjective POST channels, feedback does not increase channel capacity, thereby extending Shannon's classical result on discrete memoryless channels to a broader class of finite-state channels.

The Gist

Here is an explanation of the paper using simple language, everyday analogies, and creative metaphors.

The Big Question: Does Looking Back Help You Move Forward?

Imagine you are trying to send a secret message to a friend across a noisy, crowded room.

• The Channel: The air between you and your friend.
• The Noise: People shouting, music playing, or wind blowing.
• Feedback: Your friend shouting back, "I heard 'apple'!" or "I didn't catch that!"

In the world of information theory, there is a famous rule (Shannon's Theorem) that says: If the noise is random and forgets everything immediately (Memoryless), hearing your friend shout back doesn't help you send the message faster. You can't use their feedback to outsmart the noise because the noise doesn't care about the past.

The Big Mystery: What if the noise does remember? What if the noise today depends on what happened yesterday? Intuitively, we think: "If the noise has a memory, and I can hear what happened, I should be able to predict the noise and send messages faster!"

Most people believed this was true. But this paper proves that sometimes, even if the noise has a memory, looking back (feedback) still doesn't help you send data any faster.

---

The Stage: The "POST" Channel

The authors study a specific type of noisy channel called a POST channel.

The Analogy: The Bouncing Ball
Imagine you are throwing a ball (your message) at a wall.

• The State: The way the ball bounces depends entirely on where it landed last time.
• The Rule: If the ball hit the left side last time, the wall is slippery today. If it hit the right side, the wall is sticky today.
• The Feedback: You can see exactly where the ball landed last time.

In a standard "memoryful" channel, knowing where the ball landed last time should let you adjust your throw perfectly for today. You should be able to game the system.

The Discovery: The "Almost Forgetful" Room

The authors looked at a special version of this bouncing ball room. They called it "Approximately Memoryless."

The Analogy: The Slightly Wobbly Table
Imagine a table that is supposed to be perfectly flat (Memoryless). But, it's slightly wobbly. Sometimes it tilts left, sometimes right, but it's very close to being flat.

• The "Surjectivity" condition mentioned in the paper is like saying: "You have enough different types of balls to hit every possible spot on the table." (You have more input options than output outcomes).

The Result:
The paper proves that if your table is almost flat (approximately memoryless) and you have enough balls to cover all the spots (surjective), shouting back to your friend (feedback) gives you zero advantage.

Even though the table wobbles a tiny bit based on where the ball landed last time, you can't use that wobble to send more data. The best strategy is exactly the same as if the table were perfectly flat.

Why Does This Happen? (The Magic Trick)

Why doesn't feedback help here?

The Analogy: The Master Chef vs. The Sous-Chef

• Feedback Strategy (The Sous-Chef): Tastes the soup, realizes it's too salty, and adds water. Then tastes again, realizes it's too watery, and adds salt. They are constantly reacting to the past.
• No-Feedback Strategy (The Master Chef): Knows the recipe perfectly. They don't need to taste the soup to know how much salt to add because the ingredients are so consistent that the recipe works every time.

In this specific "wobbly table" scenario, the "Master Chef" (the non-feedback strategy) can already predict the outcome perfectly well. The "Sous-Chef" (the feedback strategy) thinks they are doing something clever by reacting to the past, but they are actually just doing the exact same thing the Master Chef was doing all along.

The paper shows that for these specific channels, the "wobble" is so small and the "balls" are so versatile that the feedback loop doesn't unlock any new secrets. The system is already running at maximum efficiency without looking back.

The "Surjectivity" Rule: Why It Matters

The paper mentions a condition called Surjectivity.

The Analogy: The Key and the Lock
Imagine you have a set of keys (Inputs) and a set of locks (Outputs).

• Surjective: You have at least as many keys as locks. You can open every single lock.
• Not Surjective: You have fewer keys than locks. Some locks can never be opened.

The paper says: If you have enough keys to open every lock, feedback is useless.
But if you have fewer keys than locks, the story changes. In that case, the "wobble" of the table might actually help you squeeze through a crack you couldn't reach before. Feedback becomes a superpower only when you are running out of options.

The Takeaway

1. Shannon was right, but the story is bigger: We used to think "No Feedback Gain" only happened in perfectly random, forgetful channels. This paper says: No, it happens in a huge family of channels that are almost random.
2. Memory isn't always a superpower: Just because a system has a memory (it remembers the past) doesn't mean you can use that memory to cheat the system. Sometimes, the memory is just a tiny, irrelevant wobble.
3. The "Almost" is powerful: Even if a channel isn't perfectly memoryless, as long as it's "close enough" and you have enough input options, you don't need feedback to get the best speed.

In a nutshell: If your communication channel is "mostly forgetful" and you have enough tools to talk to it, looking back at what happened yesterday won't help you talk faster today. You're already doing the best you can.

Technical Summary

Here is a detailed technical summary of the paper "Feedback Does Not Increase the Capacity of Approximately Memoryless Surjective POST Channels" by Zhang, Chen, and Wang.

1. Problem Statement

The paper addresses a fundamental question in information theory: Does feedback increase the capacity of channels with memory?

• Context: Shannon's classical theorem states that feedback does not increase the capacity of Discrete Memoryless Channels (DMCs). However, for channels with memory, it is generally believed that feedback allows the encoder to adapt to the channel state, thereby increasing capacity.
• Specific Model: The authors study POST (Previous Output Serves as the current state) channels. In these finite-state channels, the state at time $t$ is the output at time $t-1$ ($Y_{t-1}$). The transition probability is $Q(y_t | x_t, y_{t-1})$.
• Core Question: Under what conditions does a POST channel with memory exhibit the same property as a DMC, where feedback provides no capacity gain? The authors focus on approximately memoryless POST channels, where the state-dependent transition matrices are sufficiently close to a fixed memoryless reference channel.

2. Methodology and Theoretical Framework

A. Definitions and Setup

• Approximately Memoryless: A POST channel $Q$ is defined as $W$-centered $\delta$-approximately memoryless if its state-dependent transition matrices $Q^{(c)}_{y'}$ are within a distance $\delta$ (in infinity norm) of a memoryless reference channel $W$.
• Surjectivity Condition: The reference channel $W$ must satisfy a "surjectivity" condition. This involves:
  1. Strict Complementary Slackness: The capacity-achieving input distribution $P_X^{(W)}$ is unique and strictly positive on a subset $S \subseteq \mathcal{X}$ where $|S| = |\mathcal{Y}|$.
  2. Full Rankness: The submatrix of $W$ corresponding to columns in $S$ has full rank.
  • Note: This condition essentially requires the input alphabet size $|\mathcal{X}|$ to be at least the output alphabet size $|\mathcal{Y}|$.

B. Capacity Characterizations

• Non-Feedback Capacity ($C(Q)$): Characterized as the limit of the maximum mutual information per unit time over block length $n$. For indecomposable POST channels, this is $\lim_{n \to \infty} \frac{1}{n} \max I(X^n; Y^n | Y_0)$.
• Feedback Capacity ($C_f(Q)$): Characterized by a single-letter optimization problem:
  $$C_f(Q) = \max_{P_{XY'}} I(X; Y | Y') \quad \text{s.t.} \quad P_Y = P_{Y'}$$
  where the joint distribution factors as $P_{XY'}(x, y') Q(y|x, y')$.

C. Proof Strategy

The proof of the main theorem proceeds in two main stages:

1. Case $|\mathcal{X}| = |\mathcal{Y}|$:

   • The authors show that for sufficiently small $\delta$, the optimization problem for feedback capacity has a unique maximizer that converges to the product distribution $P_X^{(W)} P_Y^{(W)}$ as $\delta \to 0$.
   • Key Insight (Simulation Argument): The core of the proof is demonstrating that the output process generated by the optimal feedback strategy (a Markov process) can be simulated by a non-feedback input distribution.
   • Linear Algebraic Approach: The problem is mapped to finding a probability vector $p$ such that $Q^{(n)} p = q$, where $Q^{(n)}$ is the $n$-fold transition matrix and $q$ is the output distribution induced by feedback.
   • Because $W$ is full rank and surjective, $Q^{(n)}$ is invertible (full rank) for small $\delta$. The authors construct the inverse recursively and use induction to prove that the resulting input distribution vector $p$ remains a valid probability vector (non-negative entries) for small perturbations. This proves that the feedback-induced output process is achievable without feedback, implying $C(Q) = C_f(Q)$.

2. Case $|\mathcal{X}| > |\mathcal{Y}|$:

   • The authors prove that under the surjectivity condition, the optimal input distribution for the feedback capacity is supported only on the subset $S$ (where $|S| = |\mathcal{Y}|$).
   • This effectively reduces the problem to the equal-alphabet case ($|\mathcal{X}| = |\mathcal{Y}|$), which was already solved.

3. Key Contributions and Results

• Main Theorem (Theorem 1): For any memoryless surjective channel $W$, there exists a $\delta > 0$ such that for all $W$-centered $\delta$-approximately memoryless POST channels $Q$, the feedback capacity equals the non-feedback capacity ($C(Q) = C_f(Q)$).
• Extension of Shannon's Theorem: This result generalizes Shannon's theorem. It shows that the "no feedback gain" property is not unique to strictly memoryless channels but extends to a broad class of channels with memory that are "close" to memoryless and satisfy structural surjectivity.
• Necessity of Surjectivity and Alphabet Size:
  • The paper demonstrates via counter-examples (Examples 1 and 2) that if $|\mathcal{X}| < |\mathcal{Y}|$ or if the channel is rank-deficient, the output distribution induced by feedback may lie outside the convex hull of the non-feedback transition matrices. In such cases, feedback does increase capacity.
  • This highlights that the ability to simulate the feedback process without feedback relies on the input space having enough degrees of freedom to cover the output space.

4. Significance and Implications

• Fundamental Insight: The paper challenges the intuition that "memory always implies feedback gain." It identifies a specific geometric and algebraic regime (approximate memorylessness + surjectivity) where the encoder cannot gain an advantage from knowing the past output because the channel dynamics are too close to a memoryless structure where i.i.d. inputs are already optimal.
• Geometric Interpretation: The authors provide a clear geometric interpretation: Feedback capacity exceeds non-feedback capacity only if the optimal feedback output distribution lies outside the convex hull of the columns of the channel transition matrix. For approximately memoryless surjective channels, the convex hull is large enough (due to full rank and input dominance) to contain the feedback-induced distribution.
• Broader Applications: The authors suggest that the core idea—simulating a closed-loop (feedback) process with an open-loop (non-feedback) process—has implications beyond information theory, potentially relating to Partially Observable Markov Decision Processes (POMDPs) and Reinforcement Learning.
• Future Directions: The paper notes that the "approximately memoryless" condition is a technical convenience. The phenomenon likely holds for a wider class of channels, and finding the exact boundary (perturbation bounds) where feedback starts to provide gain is an open problem.

Summary Conclusion

Zhang, Chen, and Wang establish that for a wide class of finite-state channels (POST channels) that are structurally close to memoryless channels and satisfy a surjectivity condition (input alphabet $\ge$ output alphabet), feedback provides no capacity gain. They prove this by showing that the optimal feedback strategy's output statistics can be perfectly replicated by a non-feedback strategy, effectively reducing the capacity of these "nearly memoryless" channels to that of their memoryless counterparts. This result significantly broadens the scope of Shannon's classic theorem.