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 Q. We also show that if an f (p)-coin can be simulated by a pushdown automaton, then f is an algebraic function over Q; however, pushdown automata can simulate f (p)-coins for certain non-rational functions such as f (p) = √ p. 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.
Mossel, Peres, and Hillar REF characterize the set of functions f : (0, 1) → (0, 1) for which it is possible to simulate an f (p)-biased coin with a p-biased coin when p is unknown.
New coins from old : computing with unknown bias
Combinatorial Algorithms on Words, ed. A. Apostolico and Z. Galil, NATO ASI SERIES, Springer-Verlag
Mathematics Computer Science