ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.