An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series

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:
  • Mendo Tomás, Luis
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

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (296kB) | Preview

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: http://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
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM