Cascade-channel capacity conjecture for finite-state channels

About 10 years old · traced to

Let p(y(i),s(i+1)∣x(i),s(i))p(y(i),s(i+1)\mid x(i),s(i)) be a state-dependent channel with finite input and output alphabets satisfying ∣X∣=∣Y∣<∞|\mathcal X|=|\mathcal Y|<\infty. For a channel with memory, let C0C_0 denote its zero-error capacity, let C0mC_0^m denote the zero-error capacity of the mm-fold cascade channel, and define

C0inf⁡=lim⁡m→∞C0m.C_0^{\inf}=\lim_{m\to\infty}C_0^m.

Cascade-channel capacity conjecture. If ∣S∣<∞|\mathcal S|<\infty, so that the channel is finite-state, then the Shannon capacity of the mm-fold cascade channel converges to C0inf⁡C_0^{\inf} as m→∞m\to\infty. Conversely, there exist channels with finite input and output alphabets and infinite state space ∣S∣=∞|\mathcal S|=\infty for which the Shannon capacity of the cascade channel converges, as m→∞m\to\infty, to a value strictly larger than C0inf⁡C_0^{\inf}.

The conjecture distinguishes finite-state channels, where asymptotic cascade capacity is predicted to equal the limiting zero-error capacity, from channels with infinite memory, where a strict separation can occur. The supplied text gives no resolution, so the conjecture remains open.

References

Primary source

Amin Gohari, Mahtab Mirmohseni and Masoumeh Nasiri-Kenari, “Information Theory of Molecular Communication: Directions and Challenges”, arXiv:1612.03360 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.