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

VL - 65

SP - 8067

EP - 8083

JO - IRE Professional Group on Information Theory

JF - IRE Professional Group on Information Theory

SN - 0018-9448

IS - 12

M1 - 8725594

ER -