TY - JOUR
T1 - Sharp bounds for mutual covering
AU - Liu, Jingbo
AU - Yassaee, Mohammad Hossein
AU - Verdu, Sergio
N1 - Funding Information:
Manuscript received January 1, 2019; revised April 16, 2019; accepted May 9, 2019. Date of publication May 29, 2019; date of current version November 20, 2019. This work was supported in part by NSF Grant CCF-1016625 and Grant CCF-0939370, and in part by the Center for Science of Information. J. Liu was supported by the Wallace Memorial Fellowship at Princeton University. This paper was presented at the 2017 IEEE International Symposium on Information Theory (ISIT).
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2019/12
Y1 - 2019/12
N2 - A fundamental tool in network information theory is the covering lemma, which lower bounds the probability that there exists a pair of random variables; among a given number of independently generated candidates, falling within a given set. We use a weighted sum trick and Talagrand's concentration inequality to prove new mutual covering bounds. We identify two interesting applications: 1) when the probability of the set under the given joint distribution is bounded away from 0 and 1, the covering probability converges to 1 doubly exponentially fast in the blocklength, which implies that the covering lemma does not induce penalties on the error exponents in the applications to coding theorems; and 2) using Hall's marriage lemma, we show that the maximum difference between the probability of the set under the joint distribution and the covering probability equals half the minimum total variation distance between the joint distribution and any distribution that can be simulated by selecting a pair from the candidates. Thus we use the mutual covering bound to derive the exact error exponent in the joint distribution simulation problem. In both applications, the determination of the exact exponential (or double exponential) behavior relies crucially on the sharp concentration inequality used in the proof of the mutual covering lemma.
AB - A fundamental tool in network information theory is the covering lemma, which lower bounds the probability that there exists a pair of random variables; among a given number of independently generated candidates, falling within a given set. We use a weighted sum trick and Talagrand's concentration inequality to prove new mutual covering bounds. We identify two interesting applications: 1) when the probability of the set under the given joint distribution is bounded away from 0 and 1, the covering probability converges to 1 doubly exponentially fast in the blocklength, which implies that the covering lemma does not induce penalties on the error exponents in the applications to coding theorems; and 2) using Hall's marriage lemma, we show that the maximum difference between the probability of the set under the joint distribution and the covering probability equals half the minimum total variation distance between the joint distribution and any distribution that can be simulated by selecting a pair from the candidates. Thus we use the mutual covering bound to derive the exact error exponent in the joint distribution simulation problem. In both applications, the determination of the exact exponential (or double exponential) behavior relies crucially on the sharp concentration inequality used in the proof of the mutual covering lemma.
KW - concentration inequalities
KW - covering lemmas
KW - distribution simulation
KW - information density
KW - network information theory
KW - one-shot method
KW - randomness generation
KW - rejection sampling
KW - Shannon theory
UR - http://www.scopus.com/inward/record.url?scp=85077499211&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85077499211&partnerID=8YFLogxK
U2 - 10.1109/TIT.2019.2919720
DO - 10.1109/TIT.2019.2919720
M3 - Article
AN - SCOPUS:85077499211
SN - 0018-9448
VL - 65
SP - 8067
EP - 8083
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 12
M1 - 8725594
ER -