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 capacity \(C_{\mathrm{det}}\), measured in bits per channel use.
Criterion. Maximal or average error under every state sequence, in the standard unconstrained finite AVC setting.
- Finite alphabets and no state-cost constraint.
- The adversary knows the code but not the message or encoder randomness.
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\).
| 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 |
Lean formalization
Canonical statementNone
Version 1 · Lean. Adversarial state sequences and symmetrizability are high-value shared definitions.
Substantial proofs0 linked
No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.
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.
Discussion
Thread key: capacityatlas:arbitrarily-varying-discrete-memoryless-channel