TY - GEN

T1 - Rejection Sampling and Noncausal Sampling under Moment Constraints

AU - Liu, Jingbo

AU - Verdu, Sergio

N1 - Funding Information:
This work is supported by NSF grants CCF-1350595, CCF-1016625, CCF-0939370, and DMS-1148711, by ARO Grants W911NF-15-1-0479 and W911NF-14-1-0094, and AFOSR FA9550-15-1-0180, and by the Center for Science of Information. We thank Professor Elchanan Mossel for suggesting the streaming version in the end of Section I.
Funding Information:
This work is supported by NSF grants CCF-1350595, CCF- 1016625, CCF-0939370, and DMS-1148711, by ARO Grants W911NF-15-1-0479 and W911NF-14-1-0094, and AFOSR FA9550-15-1-0180, and by the Center for Science of Information.
Publisher Copyright:
© 2018 IEEE.

PY - 2018/8/15

Y1 - 2018/8/15

N2 - In the rejection sampling problem, a sequence of samples distributed according to Q are observed sequentially by a sampler which stops and makes the selection at a certain point so that the selected sample is distributed according to P. Harsha-Jain-McAllester-Radhakrishnan showed that the expected length of a variable-length compression of the index of the selected sample is approximately D(PVert Q). We prove Renyi generalizations of their result under some regularity conditions on the information spectrum. It turns out that causality matters except for Renyi divergence of order 1. For alphain(0,1), the minimum alpha -moment of the selected index is approximately exp left(alpha D- frac 1 1-alpha(PVert Q)right) · In contrast, in the variant where the sequence is observed noncausally, the minimum alpha -moment ((alphageq 0) is approximately exp(alpha D- 1+alpha(PVert Q)). The proof is based on a simple optimization duality between sampling and covering.

AB - In the rejection sampling problem, a sequence of samples distributed according to Q are observed sequentially by a sampler which stops and makes the selection at a certain point so that the selected sample is distributed according to P. Harsha-Jain-McAllester-Radhakrishnan showed that the expected length of a variable-length compression of the index of the selected sample is approximately D(PVert Q). We prove Renyi generalizations of their result under some regularity conditions on the information spectrum. It turns out that causality matters except for Renyi divergence of order 1. For alphain(0,1), the minimum alpha -moment of the selected index is approximately exp left(alpha D- frac 1 1-alpha(PVert Q)right) · In contrast, in the variant where the sequence is observed noncausally, the minimum alpha -moment ((alphageq 0) is approximately exp(alpha D- 1+alpha(PVert Q)). The proof is based on a simple optimization duality between sampling and covering.

UR - http://www.scopus.com/inward/record.url?scp=85052486025&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052486025&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2018.8437857

DO - 10.1109/ISIT.2018.8437857

M3 - Conference contribution

AN - SCOPUS:85052486025

SN - 9781538647806

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1565

EP - 1569

BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018

Y2 - 17 June 2018 through 22 June 2018

ER -