New coins from old: computing with unknown bias

We are interested in a generalization of a problem considered by Von
Neumann: Is it possible to simulate a coin with bias f(p) given an
independent sequence of coins with (unknown) bias p, where f : (0,1)
-> (0,1)?

We show that f(p) can be simulated by a finite automaton if and only if
it is a rational function. We show that if f(p) is simulated by a
pushdown automaton, then f is algebraic, and construct pushdown automata
simulating non-rational functions.

We will also discuss how this model is related to the Chomsky
Schutzenberger theory, exact sampling and the theory of computability.

Joint work with Yuval Peres