Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1612.08923 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913583962521600 |
|---|---|
| author | Mendo, Luis |
| author_facet | Mendo, Luis |
| contents | Given a sequence of independent Bernoulli variables with unknown parameter $p$, and a function $f$ expressed as a power series with non-negative coefficients that sum to at most $1$, an algorithm is presented that produces a Bernoulli variable with parameter $f(p)$. In particular, the algorithm can simulate $f(p)=p^a$, $a\in(0,1)$. For functions with a derivative growing at least as $f(p)/p$ for $p\rightarrow 0$, the average number of inputs required by the algorithm is asymptotically optimal among all simulations that are fast in the sense of Nacu and Peres. A non-randomized version of the algorithm is also given. Some extensions are discussed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1612_08923 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series Mendo, Luis Statistics Theory 65C50, 62L G.3 Given a sequence of independent Bernoulli variables with unknown parameter $p$, and a function $f$ expressed as a power series with non-negative coefficients that sum to at most $1$, an algorithm is presented that produces a Bernoulli variable with parameter $f(p)$. In particular, the algorithm can simulate $f(p)=p^a$, $a\in(0,1)$. For functions with a derivative growing at least as $f(p)/p$ for $p\rightarrow 0$, the average number of inputs required by the algorithm is asymptotically optimal among all simulations that are fast in the sense of Nacu and Peres. A non-randomized version of the algorithm is also given. Some extensions are discussed. |
| title | An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series |
| topic | Statistics Theory 65C50, 62L G.3 |
| url | https://arxiv.org/abs/1612.08923 |