Abstract:
We find necessary and sufficient conditions under which the capacity $C_L$ of an arbitrarily varying channel (AVC), for deterministic codes with decoding into a list of size $L$ and for the average error probability criterion, equals the capacity $C_r$ of the AVC for random codes. For binary AVCs, we prove the existence of a finite $L^\ast<\infty$ such that $_L=C_r$ for all $L>L^\ast$.