Full text
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (296kB) | Preview |
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.
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 |
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (296kB) | Preview |
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.
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 |