New Coins From Old: Computing With Unknown Bias

Elchanan Mossel, Yuval Peres

TL;DR

This paper explores the fascinating question of how to generate a coin with a desired bias $f(p)$ from a sequence of coin flips with an unknown bias $p$. The authors prove that a finite automaton can simulate an $f(p)$-coin if and only if $f$ is a rational function over the rational numbers. They also show that pushdown automata can simulate algebraic functions, but not all algebraic functions can be simulated by pushdown automata.

What Problem Does This Paper Address?

Imagine you have a coin with a bias $p$ (meaning it lands heads with probability $p$), but you don't know what $p$ is. You want to use this coin to simulate a new coin with a bias $f(p)$, where $f$ is some function. This is like having a "black box" coin and wanting to produce another "black box" coin with a specific, but unknown, bias. The core problem is to determine which functions $f$ allow for such a simulation, and what computational models are sufficient for it. This is a generalization of von Neumann's classic method for generating an unbiased coin ($f(p) = 1/2$) from a biased coin. The paper investigates the relationship between the computational power of the simulation scheme (finite automaton, pushdown automaton) and the algebraic properties of the function $f$.

Methods

The paper's main contribution lies in establishing a precise characterization of functions that can be simulated by finite automata. The key result is that an $f(p)$-coin can be simulated by a finite automaton if and only if $f$ is a rational function over the rational numbers. This is proven by showing that finite automata simulations correspond to "block simulations," which in turn are equivalent to rational functions.

For more powerful simulation models, the paper explores pushdown automata. They prove that if a function $f$ can be simulated by a pushdown automaton, then $f$ must be an algebraic function. This is achieved by relating the simulation process to solutions of polynomial equations. The paper also constructs pushdown automata that can simulate non-rational functions, such as $f(p) = \sqrt{p}$, demonstrating that pushdown automata are more powerful than finite automata in this context.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Rationality is Key for Finite Automata: The most striking result is the equivalence between finite automaton simulation and rational functions. This provides a clear criterion for when a simple computational model can achieve a desired bias transformation.
  • Algebraic Functions and Pushdown Automata: The paper establishes a connection between pushdown automata and algebraic functions, showing that the former can simulate the latter. This broadens the scope of computable biases beyond rational functions.
  • Pushdown Automata Beyond Algebraic: The construction of a pushdown automaton for $\sqrt{p}$ highlights that pushdown automata can simulate functions that are not necessarily algebraic over $\mathbb{Q}$ (though $\sqrt{p}$ is algebraic over $\mathbb{Q}(p)$). This suggests a nuanced relationship between algebraic properties and simulation capabilities.
  • The Power of Computational Models: The work elegantly connects the expressive power of computational models (finite automata, pushdown automata) to the mathematical properties of the functions they can simulate.

Key Results

  • An $f(p)$-coin can be simulated by a finite automaton if and only if $f$ is the restriction to $D \subset (0,1)$ of a rational function $F$ over $\mathbb{Q}$, such that $0 < F(x) < 1$ for $0 < x < 1$.
  • If an $f(p)$-coin can be simulated by a pushdown automaton for all $p \in (0,1)$, then $f$ is an algebraic function over $\mathbb{Q}$.
  • The paper provides explicit constructions for finite automata simulating rational functions like $f(p) = 1/2$, $f(p) = p^2$, and $f(p) = p^2 / (p^2 + (1-p)^2)$.
  • A pushdown automaton is constructed to simulate $f(p) = \sqrt{p}$.

Limitations and Future Work

  • Pushdown Automata and All Algebraic Functions: The paper poses an open problem: can all algebraic functions $f: (0,1) \to (0,1)$ be simulated by a pushdown automaton? The current results show that pushdown automata can simulate algebraic functions, but it's not proven that they can simulate all of them.
  • Automaton Size: For rational functions, the paper doesn't provide bounds on the size of the finite automaton required for simulation. This is identified as a potential area for future research.
  • Generalization to k-sided Coins: The paper briefly discusses extensions to k-sided coins (dice) and suggests that similar results regarding rationality and algebraic properties hold. Further exploration in this direction is implied.
  • Exact Sampling Connection: The authors highlight the connection of their work to the theory of exact sampling, suggesting that their results can be used to construct samples from complex distributions. This is a promising avenue for future applications.

Summary updated

Abstract

Suppose that we are given a function f : (0,1) -&gt; (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.
BibTeX
@article{mossel2005new,
  author = {Elchanan Mossel and Yuval Peres},
  title = {{New Coins From Old: Computing With Unknown Bias}},
  journal = {Comb.},
  year = {2005},
  doi = {10.1007/s00493-005-0043-1},
}
Figure