Since Thomas just mentioned the topic, I'll point out this paper, just posted to the arXiv:
Paper: math.PR/0304143 From: Elchanan Mossel <mossel@stat.berkeley.edu> Date: Thu, 10 Apr 2003 20:56:46 GMT (25kb)
Title: New coins from old: computing with unknown bias Authors: Elchanan Mossel and Yuval Peres Comments: 3 figures, appendix by Christopher Hillar Subj-class: Probability Theory; Combinatorics \\ Suppose that we are given a function f : (0,1) -> (0,1) and, for some unknown p in (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 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 in (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 the square root of 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. \\ ( http://arXiv.org/abs/math/0304143 , 25kb)
--Michael Kleber kleber@brandeis.edu