Rejection Sampling and Noncausal Sampling under Moment Constraints

Jingbo Liu, Sergio Verdu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Symposium on Information Theory, ISIT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1565-1569
Number of pages5
ISBN (Print)9781538647806
DOIs
StatePublished - Aug 15 2018
Event2018 IEEE International Symposium on Information Theory, ISIT 2018 - Vail, United States
Duration: Jun 17 2018Jun 22 2018

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2018-June
ISSN (Print)2157-8095

Other

Other2018 IEEE International Symposium on Information Theory, ISIT 2018
CountryUnited States
CityVail
Period6/17/186/22/18

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Rejection Sampling and Noncausal Sampling under Moment Constraints'. Together they form a unique fingerprint.

  • Cite this

    Liu, J., & Verdu, S. (2018). Rejection Sampling and Noncausal Sampling under Moment Constraints. In 2018 IEEE International Symposium on Information Theory, ISIT 2018 (pp. 1565-1569). [8437857] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2018-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2018.8437857