ABSTRACT


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 nonrational 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 Return to Applied Math Colloquium home page 