# Tight simulation of a distribution using conditional samples

arXiv: https://arxiv.org/abs/2506.18444 · HTML: https://mlsanity.com/paper/2506.18444/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2025.

## Built on by (most cited first, 1 of 1)

- [Total Variation Distance Estimation in Autoregressive Models](https://mlsanity.com/paper/2607.19510/) (2026)

## Abstract (arXiv)

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 sample complexity is O(log2 N / varepsilon2) prefix conditional samples per query, which improves on the previously known tildeO(log3 N / varepsilon2) (Kumar, Meel and Pote, 2025). Moreover, our simulating distribution is O(varepsilon2)-close to the input distribution with respect to the Kullback-Leibler divergence, which is stricter than the usual guarantee of being O(varepsilon)-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 ± varepsilon)-multiplicative error must make Omega(log2 N / varepsilon2) prefix conditional samples per element.