Paper Info
Title
Shannon Meets von Neumann: A Minimax Theorem for Channel Coding in the Presence of a Jammer
Abstract
We study the setting of channel coding over a family of channels whose state is controlled by an adversarial jammer by viewing it as a zero-sum game between a finite blocklength encoder-decoder team, and the jammer. The encoder-decoder team choose stochastic encoding and decoding strategies to minimize the average probability of error in transmission, while the jammer chooses a distribution on the state-space to maximize this probability. The min-max value of the game is equivalent to channel coding for a compound channel - we call this the Shannon solution of the problem. The max-min value corresponds to finding a mixed channel with the largest value of the minimum achievable probability of error. When the min-max and max-min values are equal, the problem is said to admit a saddle-point or von Neumann solution. While a Shannon solution always exists, the communicating team’s problem is nonconvex for finite blocklengths, whereby a von Neumann solution may not exist. Despite this, we show that the min-max and max-min values become equal asymptotically in the large blocklength limit, for all but finitely many rates. We explicitly characterize this limiting value as a function of the rate and obtain tight finite blocklength bounds on the min-max and max-min value. As a corollary we get an explicit expression for the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline-formula> -capacity of a compound channel under stochastic codes - the first such result, to the best of our knowledge. Our results demonstrate a deeper relation between the compound channel and mixed channel than was previously known. They also show that the conventional information-theoretic viewpoint, articulated via the Shannon solution, coincides asymptotically with the game-theoretic one articulated via the von Neumann solution. Key to our results is the derivation of new finite blocklength upper bounds on the min-max value of the game via a novel achievability scheme, and lower bounds on the max-min value obtained via the linear programming relaxation based approach we introduced in <xref ref-type="bibr" rid="ref2" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">[2]</xref> .
Year
DOI
Venue
2018
10.1109/TIT.2020.2971682
IEEE Transactions on Information Theory
Keywords
DocType
Volume
Channel coding,compound channels and mixed channels,finite blocklength bounds,linear programming relaxation,saddle-point solution
Journal
66
Issue
ISSN
Citations 
5
0018-9448
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Sharu Theresa Jose122.53
Ankur A. Kulkarni210620.95