Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence
Abstract
We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution P and a proposal distribution Q, the sender and receiver share i.i.d. Q-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly P. We introduce a new information measure Rényi channel simulation divergence Rα(P‖ Q), a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is 1/2log n+O(1).
Related
- On Inherent Privacy of Posterior Sampling: A Unified Rényi-Divergence Framework
- Exact Common Information and Exact Channel Synthesis for Correlated Discrete Sources
- How Inefficient Is Natural Gradient Descent? From Exact Optimality to Θ( \sqrt{ \log d } ) Divergence
- Exact series formulas for the capacities of the amplitude damping channel
- Monotonicity of the Rényi channel capacity under non-signaling assisted channel simulation
BibTeX
@misc{fan2026exact,
title = {{Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence}},
author = {Yijun Fan and Aaron B. Wagner},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15656},
eprint = {2610.15656},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15656},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence
AU - Yijun Fan
AU - Aaron B. Wagner
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15656
UR - https://arxiv.org/abs/2610.15656
AB - We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution P and a proposal distribution Q, the sender and receiver share i.i.d. Q-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly P. We introduce a new information measure Rényi channel simulation divergence R_α(P‖ Q), a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is 1/2log n+O(1).
ER -