Rejection Sampling and Noncausal Sampling under Moment Constraints

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.