Given a coin with probability of heads of $lambda$, sample the probability $f(lambda)$. This is the Bernoulli factory problem, and it can be solved only for certain functions $f$. (For example, flipping the coin twice and taking heads only if exactly one coin shows heads, we can simulate the probability $lambda(1-lambda)$.)
Roughly speaking, the Bernoulli factory problem can be solved for $f$ only if $f$ is continuous on (0, 1) and equals neither 0 nor 1 on the open interval (0, 1) (Keane and O’Brien 1994). This result is without regard to the (classical) computational model.
This question is about solving the Bernoulli factory problem on a restricted model, namely the model of pushdown automata (state machines with a stack) that are driven by flips of a coin and produce new probabilities. In that model, Mossel and Peres (2005) showed that a pushdown automaton can simulate a (continuous) function that maps (0, 1) to (0, 1) only if that function is algebraic over the rational numbers, as defined later. They gave a question which remains open: is the converse of that statement true?
Define a pushdown automaton as follows (see Mossel and Peres 2005, Definition 1.5, for a more precise statement). The automaton starts at a given control state and has a symbol stack that starts with at least one stack symbol. With each transition, the automaton (based on the current state, the current input symbol, and the symbol at the top of the stack)—
- determines the next state, and
- replaces the top stack symbol with zero or more stack symbols.
When the stack is empty, the automaton stops and returns either 0 or 1 based on its current state. The input symbols are each either “heads” or “tails”, are independent and identically distributed, and are the result of a coin with unknown probability of heads.
A function $f(x)$ is algebraic over the rational numbers if—
- it can be a solution of a system of polynomial equations whose coefficients are rational numbers, or equivalently,
- there is a nonzero polynomial $P(x, y)$ in two variables and whose coefficients are rational numbers, such that $P(x, f(x)) = 0$ for every $x$ in the domain of $f$.
Thus, the questions are:
- For every $f(lambda)$ that maps $(0, 1)$ to $(0, 1)$, is continuous, and is algebraic over the rational numbers, is there a pushdown automaton that can simulate that function? If so, how can it be constructed?
- Are there general constructions for pushdown automata that can simulate a large class of algebraic functions, akin to those found in this section of a page of mine or in section 3.2 of Mossel and Peres 2005?
To be clear, this question is not quite the same as the question of which algebraic functions can be simulated by a context-free grammar (either in general or restricted to those of a certain ambiguity and/or alphabet size), and is not quite the same as the question of which probability generating functions can be simulated by context-free grammars or pushdown automata. (See also Icard 2019.)
- Keane, M. S., and O’Brien, G. L., “A Bernoulli factory”, ACM Transactions on Modeling and Computer Simulation 4(2), 1994.
- Mossel, Elchanan, and Yuval Peres. New coins from old: computing with unknown bias. Combinatorica, 25(6), pp.707-724, 2005.
- Icard, Thomas F., “Calibrating generative models: The probabilistic Chomsky–Schützenberger hierarchy.” Journal of Mathematical Psychology 95 (2020): 102308.