New coins from old: computing with unknown bias
| dc.creator | Mossel, Elchanan | |
| dc.creator | Peres, Yuval | |
| dc.date | 2003-04-10 | |
| dc.date.accessioned | 2026-07-07T04:56:46Z | |
| dc.date.available | 2026-07-07T04:56:46Z | |
| dc.description | 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. | |
| dc.description | 3 figures, appendix by Christopher Hillar | |
| dc.identifier | https://arxiv.org/abs/math/0304143 | |
| dc.identifier | http://arxiv.org/abs/math/0304143 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67047 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.title | New coins from old: computing with unknown bias | |
| dc.type | text |