Channel and question
- Input
- \(X_t\in\mathcal X\)
- Output
- \(Y_t\in\mathcal Y\)
- Law
- At each use an adversary selects \(s_t\in\mathcal S\), producing \(W_{s_t}(y_t|x_t)\).
- Quantity
- Deterministic-code average-error capacity \(C_{\mathrm{det}}\), measured in bits per channel use.
Criterion. Vanishing average decoding error uniformly over state sequences, for deterministic block codes.
- Finite nonempty alphabets and no input-cost or state-cost constraint.
- Encoding and decoding are deterministic, with no feedback or shared randomness.
- The adversary knows the code but not the uniform message. Neither terminal observes the state sequence.
- Error is averaged over messages before taking the supremum over state sequences.
Current status
\[C_{\mathrm{det}}=\begin{cases}0,&\text{if the AVC is symmetrizable},\\\max_{P_X}\min_{q\in\mathcal P(\mathcal S)}I(P_X,W_q),&\text{otherwise.}\end{cases}\]
Here \(W_q=\sum_s q(s)W_s\). This characterization fixes the average-error criterion and does not assert an identical maximal-error theorem.
| Result | Relation | Method | Year |
|---|---|---|---|
| Upper | \(C_{\mathrm{det}}=0\text{ for symmetrizable AVCs}\) | The adversary simulates competing codewords and prevents reliable identification. | 1988 |
| Exact | \(C_{\mathrm{det}}=C_{\mathrm{random}}\text{ when nonsymmetrizable}\) | Elimination of correlation converts random codes to deterministic codes. | 1978 |
Formal verification
Lean coverageFormally stated
New statements await mathematical review and proofs. The new claim uses deterministic coding and average error, with an oblivious state sequence.
Claims
- The unconstrained deterministic average-error AVC dichotomy. The jammer does not see the message.
operational-capacity· exact capacity · solved · Formally stated · v1
Lean declarations (1)
CapacityAtlas.Claims.arbitrarilyVaryingclaim · operational-capacity
lean/CapacityAtlas/Claims/AVC.lean — The unconstrained deterministic average-error AVC dichotomy. The jammer does not see the message.
References
- Rudolf Ahlswede (1978). Elimination of Correlation in Random Codes for Arbitrarily Varying Channels. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. DOI 10.1007/BF00533053.
- Imre Csiszár and Prakash Narayan (1988). The Capacity of the Arbitrarily Varying Channel Revisited. IEEE Transactions on Information Theory. DOI 10.1109/18.2627.