New coins from old: computing with unknown bias

Elchanan Mossel

Department of Statistics
U. C. Berkeley

December 9, 4:15pm


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

Return to Applied Math Colloquium home page