Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2507.00915 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
Sommario:
- Simulating an arbitrary discrete distribution $D \in [0, 1]^n$ using fair coin tosses incurs trade-offs between entropy complexity and space and time complexity. Shannon's theory suggests that $H(D)$ tosses are necessary and sufficient, but does not guarantee exact distribution. Knuth and Yao showed that a decision tree consumes fewer than $H(D) + 2$ tosses for one exact sample. Draper and Saad's recent work addresses the space and time aspect, showing that $H(D) + 2$ tosses, $O(n \log(n) \log(m))$ memory, and $O(H(D))$ operations are all it costs, where $m$ is the common denominator of the probability masses in $D$ and $n$ is the number of possible outcomes. In this paper, MichelangeRoll recycles leftover entropy to break the "$+2$" barrier. With $O((n + 1/\varepsilon) \log(m/\varepsilon))$ memory, the entropy cost of generating a ongoing sequence of $D$ is reduced to $H(D) + \varepsilon$ per sample.