Tight simulation of a distribution using conditional samples
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918453577777152 |
|---|---|
| author | Adar, Tomer |
| author_facet | Adar, Tomer |
| contents | 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(\log^2 N / \varepsilon^2)$ prefix conditional samples per query, which improves on the previously known $\tilde{O}(\log^3 N / \varepsilon^2)$ (Kumar, Meel and Pote, 2025). Moreover, our simulating distribution is $O(\varepsilon^2)$-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 \pm \varepsilon)$-multiplicative error must make $Ω(\log^2 N / \varepsilon^2)$ prefix conditional samples per element. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18444 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight simulation of a distribution using conditional samples Adar, Tomer Data Structures and Algorithms 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(\log^2 N / \varepsilon^2)$ prefix conditional samples per query, which improves on the previously known $\tilde{O}(\log^3 N / \varepsilon^2)$ (Kumar, Meel and Pote, 2025). Moreover, our simulating distribution is $O(\varepsilon^2)$-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 \pm \varepsilon)$-multiplicative error must make $Ω(\log^2 N / \varepsilon^2)$ prefix conditional samples per element. |
| title | Tight simulation of a distribution using conditional samples |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.18444 |