Tight simulation of a distribution using conditional samples

2025/06/23 by Adar, Tomer
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2506.18444

Abstract

We present an algorithm for simulating a distribution using prefix conditional samples (Adar, Fischer and Levi, 2024), as well as ``prefix-compatible'' conditional models such as the interval model (Cannone, Ron and Servedio, 2015) and the subcube model (CRS15, Bhattacharyya and Chakraborty, 2018). The conditional sample complexity is O(log² N / ε²) prefix conditional samples per query, which improves on the previously known O(log³ N / ε²) (Kumar, Meel and Pote, 2025). Moreover, our simulating distribution is O(ε²)-close to the input distribution with respect to the Kullback-Leibler divergence, which is stricter than the usual guarantee of being O(ε)-close with respect to the total-variation distance. We show that our algorithm is tight with respect to the highly-related task of estimation: every algorithm that is able to estimate the mass of individual elements within (1 ± ε)-multiplicative error must make Ω(log² N / ε²) prefix conditional samples per element.

Citations

• Optimal mass estimation in the conditional sampling model
• Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
• Distance Estimation for High-Dimensional Discrete Distributions
• Uniformity Testing over Hypergrids with Subcube Conditioning
• Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
• Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
• Testing Bayesian Networks
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Testing probability distributions using conditional samples
• On the Power of Conditional Samples in Distribution Testing

Related

• Optimal mass estimation in the conditional sampling model
• Testing probability distributions using conditional samples
• Faster Algorithms for Testing under Conditional Sampling
• On Distribution Testing in the Conditional Sampling Model
• Improving and extending the testing of distributions for\n shape-restricted properties