Full text
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (296kB) | Preview |
An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series
Citation
Mendo Tomás, Luis (2019). An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series. "Stochastic Processes and their Applications", v. 129 (n. 11); pp. 4366-4384. ISSN 0304-4149. https://doi.org/10.1016/j.spa.2018.11.017.
Description
| Title: | An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series |
|---|---|
| Author/s: |
|
| Item Type: | Article |
| Título de Revista/Publicación: | Stochastic Processes and their Applications |
| Date: | November 2019 |
| ISSN: | 0304-4149 |
| Volume: | 129 |
| Subjects: | |
| Freetext Keywords: | Bernoulli factory; simulation; power series |
| Faculty: | E.T.S.I. Telecomunicación (UPM) |
| Department: | Señales, Sistemas y Radiocomunicaciones |
| UPM's Research Group: | Tecnologías de la Información y las Comunicaciones GTIC |
| Creative Commons Licenses: | Recognition |
Abstract
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.
More information
| Item ID: | 53859 |
|---|---|
| DC Identifier: | https://oa.upm.es/53859/ |
| OAI Identifier: | oai:oa.upm.es:53859 |
| DOI: | 10.1016/j.spa.2018.11.017 |
| Deposited by: | Dr. Luis Mendo |
| Deposited on: | 07 Oct 2019 13:00 |
| Last Modified: | 07 Oct 2019 13:00 |
