I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof itself is quite dense (using Lemma 2 in the paper).

I am wondering if there is any work that proves the converse of AVC random coding capacity (shared randomness). If anyone can write the proof here then that works as well. I am ok with a proof for deterministic coding capacity of AVC as well if it is different from the above-mentioned paper.

  • 1
    $\begingroup$ Some proofs are technical. There's no way around it. $\endgroup$ Oct 7, 2020 at 18:46
  • $\begingroup$ @YuvalFilmus How about the proof for random coding (shared randomness) ? I can't seem to find it anywhere. $\endgroup$ Oct 8, 2020 at 8:06
  • 1
    $\begingroup$ Wikipedia gives a reference. Have you checked it? $\endgroup$ Oct 8, 2020 at 8:24
  • $\begingroup$ @YuvalFilmus Thanks a lot. 'Reliable Communication Under Channel Uncertainty' gives a comprehensive survey that helped me find the desired proof. Don't know why it didn't show up in google search. $\endgroup$ Oct 8, 2020 at 12:40

1 Answer 1


A complete proof appears in Blackwell, Breiman and Thomasian, The Capacities of Certain Channel Classes Under Random Coding. This paper is linked from the Wikipedia article on AVCs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.