Cascade-channel capacity conjecture for finite-state channels

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=limmC0m.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 C0infC_0^{\inf} as mm\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 mm\to\infty, to a value strictly larger than C0infC_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.

Sources & referencesView supporting material

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.