New coins from old: computing with unknown bias

Elchanan Mossel, Yuval Peres

Abstract

Suppose that we are given a function $f : (0,1) \to (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 $\mathbb{Q}$. We also show that if an $f(p)$-coin can be simulated by a pushdown automaton, then $f$ is an algebraic function over $\mathbb{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.

Introduction: The Simulation Problem

Imagine you have a "broken" coin that comes up heads with some unknown probability $p$. You want to use this coin to simulate a new coin that comes up heads with probability $f(p)$.

A famous solution to a specific version of this problem comes from John von Neumann (1951). He showed that if you want a fair coin ($f(p) = 1/2$), you can just toss your biased coin in pairs: if you get "Heads-Tails," output 0; if "Tails-Heads," output 1; if you get "Heads-Heads" or "Tails-Tails," throw them away and try again. This works regardless of what $p$ actually is. This procedure can be represented as a simple finite automaton.

A finite automaton implementing von Neumann's trick to simulate a fair coin (f(p) = 1/2) from a p-biased coin.

The authors of this paper ask a broader question: For which functions $f$ is this possible if we restrict our "simulator" to specific types of computers? While previous researchers (Keane and O’Brien, 1994) looked at what is possible with infinite computational power, this paper focuses on restricted models like Finite Automata (no extra memory) and Pushdown Automata (memory in the form of a stack).

Methods

The authors bridge the gap between probability theory and formal language theory. By defining simulation schemes as automata that read a stream of i.i.d. Bernoulli($p$) bits and halt with an output bit, they can leverage the structural properties of these machines.

  • Automata Theory: They define simulation schemes using Finite Automata (FA) and Pushdown Automata (PDA). These machines take a sequence of coin tosses as input and must eventually stop and output a 0 or 1.
  • Harmonic Functions: To analyze Finite Automata, they treat the states of the automaton as nodes in a graph and the probability of reaching an output state as a harmonic function. The probability of the machine outputting a '1' is then the solution to a system of linear equations with coefficients in $\mathbb{Q}(p)$.
  • Algebraic Geometry: In the appendix, they use tools from real algebraic geometry (like the Tarski-Seidenberg Theorem) to prove that functions simulated by PDAs must be algebraic.
  • Pólya’s Theorem: They use a result by George Pólya regarding positive polynomials to prove that any valid rational function can indeed be simulated by a finite automaton.

Key Insights: Computational Power vs. Mathematical Complexity

There is a direct correspondence between the "intelligence" of the machine and the "algebraic complexity" of the function it can produce.

Finite Automata and Rational Functions

If your machine has a fixed, finite amount of memory, it can only simulate functions that look like ratios of polynomials (e.g., $f(p) = p^2 / (p^2 + (1-p)^2)$). This means that the probability of the machine outputting a '1' is a rational function of the input bias $p$. The structure of the automaton dictates that the output probability must satisfy a linear recurrence, which always yields a rational solution.

A finite automaton simulating the rational function f(p) = p^2 / (p^2 + (1-p)^2).

Pushdown Automata and Algebraic Functions

If you add a stack (allowing the machine to "count" or remember nested structures), you can simulate algebraic functions (e.g., $\sqrt{p}$). The "Ladder Graph" construction is a particularly elegant part of the proof. It shows that while a finite automaton is "trapped" in a finite state space, a PDA can use its stack to simulate a random walk on an infinite graph. By carefully designing the transitions such that the probability of moving "up" or "down" the ladder depends on $p$, the machine can eventually halt with a probability that involves a square root, a feat impossible for any machine with only finite memory.

Crucially, the simulation scheme (the automaton) must be the same regardless of the value of $p$. The machine doesn't "know" $p$; it just reacts to the stream of bits.

Key Results

  • Theorem 1.1: A function $f(p)$ can be simulated by a finite automaton if and only if $f$ is a rational function over $\mathbb{Q}$ such that $0 < f(p) < 1$ for all $p \in (0,1)$.
  • Theorem 1.2: If a function $f(p)$ can be simulated by a pushdown automaton, then $f$ must be an algebraic function (it is the root of a polynomial whose coefficients are polynomials in $p$).
  • Constructive Proof for $\sqrt{p}$: The authors explicitly show that while a finite automaton cannot simulate the square root of the bias, a pushdown automaton can. This provides a concrete example of how adding a stack increases the "statistical reach" of a computer.

Limitations and Future Work

While the authors prove that PDA-simulatable functions must be algebraic, the converse remains an open question: can every algebraic function (within the $(0,1)$ range) be simulated by a pushdown automaton?

Additionally, the paper focuses on computability rather than efficiency. For rational functions, there is no simple bound on the number of states needed in an automaton. A suggested open problem is finding an efficient algorithm to determine the smallest possible automaton for a given rational function, which may involve deep properties of number theory.

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},
}

Loading related content...

Figure