New Coins From Old: Computing With Unknown Bias |
| |
Authors: | Elchanan Mossel Yuval Peres? |
| |
Institution: | (1) University of California, Berkeley, 367 Evans Hall, Berkeley, CA 94720-3860, USA;(2) University of California, Berkeley, 367 Evans Hall, Berkeley, CA 94720-3860, USA |
| |
Abstract: | Suppose that we are given a function f : (0, 1)→(0,1) and, for some unknown p∈(0, 1), a sequence of independent tosses of a p-coin (i.e., a coin with probability p of “heads”). For which functions f is it possible to simulate an f(p)-coin? This question was raised by S. Asmussen and J. Propp. A simple simulation scheme for the constant function f(p)≡1/2 was described by von Neumann (1951); this scheme can be easily implemented using a finite automaton. We prove that in
general, an f(p)-coin can be simulated by a finite automaton for all p ∈ (0, 1), if and only if f is a rational function over ℚ. We also show that if an f(p)-coin can be simulated by a pushdown automaton, then f is an algebraic function over ℚ; however, pushdown automata can simulate f(p)-coins for certain nonrational functions such as
. These results complement the work of Keane and O’Brien (1994), who determined the functions f for which an f(p)-coin can be simulated when there are no computational restrictions on the simulation scheme.
* Supported by a Miller Fellowship.
† Supported in part by NSF Grant DMS-0104073 and by a Miller Professorship.
‡ This work is supported under a National Science Foundation Graduate Research Fellowship. |
| |
Keywords: | 68Q70 14P10 65C50 |
本文献已被 SpringerLink 等数据库收录! |
|