New coins from old: computing with unknown bias

Details New coins from old: computing with unknown bias New coins from old: computing with unknown bias

2003-04-10

arxiv.org/abs/math/0304143v1

Mathematics

Probability

3 figures, appendix by Christopher Hillar

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

New coins from old: computing with unknown bias does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New coins from old: computing with unknown bias, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New coins from old: computing with unknown bias will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-411347