-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathbernreq.html
More file actions
313 lines (244 loc) · 42.6 KB
/
bernreq.html
File metadata and controls
313 lines (244 loc) · 42.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
<!DOCTYPE html><html xmlns:dc="http://purl.org/dc/terms/" xmlns:og="http://ogp.me/ns#" ><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><title>Open Questions on the Bernoulli Factory Problem</title><meta name="citation_pdf_url" content="https://peteroupc.github.io/bernreq.pdf"><meta name="citation_url" content="https://peteroupc.github.io/bernreq.html"><meta name="citation_title" content="Open Questions on the Bernoulli Factory Problem"><meta name="dc.date" content="2026-04-16"><meta name="citation_date" content="2026/04/16"><meta name="citation_publication_date" content="2026/04/16"><meta name="citation_online_date" content="2026/04/16"><meta name="og:title" content="Open Questions on the Bernoulli Factory Problem"><meta name="og:type" content="article"><meta name="og:url" content="https://peteroupc.github.io/bernreq.html"><meta name="og:site_name" content="peteroupc.github.io"><meta name="dc.format" content="text/html"><meta name="dc.language" content="en"><meta name="title" content="Open Questions on the Bernoulli Factory Problem"><meta name="dc.title" content="Open Questions on the Bernoulli Factory Problem"><meta name="twitter:title" content="Open Questions on the Bernoulli Factory Problem"><meta name="dc.creator" content="Peter Occil"/><meta name="author" content="Peter Occil"/><meta name="citation_author" content="Peter Occil"/><meta name="viewport" content="width=device-width"><link rel=stylesheet type="text/css" href="/style.css">
<script type="text/x-mathjax-config"> MathJax.Hub.Config({"HTML-CSS": { availableFonts: ["STIX","TeX"], linebreaks: { automatic:true }, preferredFont: "TeX" },
tex2jax: { displayMath: [ ["$$","$$"], ["\\[", "\\]"] ], inlineMath: [ ["$", "$"], ["\\\\(","\\\\)"] ], processEscapes: true } });
</script><script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS_HTML-full"></script></head><body> <div class="header">
<nav><p><a href="#navigation">Menu</a> - <a href="#top">Top</a> - <a href="/">Home</a></nav></div>
<div class="mainarea" id="top">
<h1 id="open-questions-on-the-bernoulli-factory-problem">Open Questions on the Bernoulli Factory Problem</h1><p>This version of the document is dated 2026-04-16. <a href='https://github.com/peteroupc/peteroupc.github.io/issues'>Post an issue or comment on this document</a>.</p>
<p><a href="mailto:poccil14@gmail.com"><strong>Peter Occil</strong></a></p>
<p><a id="Background"></a></p>
<h2 id="background">Background</h2>
<p>Suppose there is a coin that shows heads with an unknown probability, $\lambda$. The goal is to use that coin (and possibly also a fair coin) to build a “new” coin that shows heads with a probability that depends on $\lambda$, call it $f(\lambda)$. This is the <em>Bernoulli factory problem</em>, and it can be solved for a function $f(\lambda)$ only if it’s continuous. (For example, flipping the coin twice and taking heads only if exactly one coin shows heads, the probability $2\lambda(1-\lambda)$ can be simulated.)</p>
<p>This page contains several questions about the <a href="https://peteroupc.github.io/bernoulli.html"><strong>Bernoulli factory</strong></a> problem. Answers to them will greatly improve my pages on this site about Bernoulli factories. If you can answer any of them, post an issue in the <a href="https://github.com/peteroupc/peteroupc.github.io/issues"><strong>GitHub issues page</strong></a>.</p>
<blockquote>
<p><strong>Note:</strong> The Bernoulli factory problem is a special case of a more general mathematical problem that I call “<a href="https://peteroupc.github.io/sampling.html"><strong>The Sampling Problem</strong></a>”.</p>
</blockquote>
<p><a id="Contents"></a></p>
<h2 id="contents">Contents</h2>
<ul>
<li><a href="#Background"><strong>Background</strong></a></li>
<li><a href="#Contents"><strong>Contents</strong></a></li>
<li><a href="#Polynomials_that_approach_a_Bernoulli_factory_function_fast"><strong>Polynomials that approach a Bernoulli factory function “fast”</strong></a>
<ul>
<li><a href="#Main_Question"><strong>Main Question</strong></a></li>
<li><a href="#Solving_the_Bernoulli_factory_problem_with_polynomials"><strong>Solving the Bernoulli factory problem with polynomials</strong></a></li>
<li><a href="#A_Matter_of_Efficiency"><strong>A Matter of Efficiency</strong></a></li>
<li><a href="#A_Conjecture_on_Polynomial_Approximation"><strong>A Conjecture on Polynomial Approximation</strong></a></li>
<li><a href="#Strategies"><strong>Strategies</strong></a></li>
</ul>
</li>
<li><a href="#Other_Questions"><strong>Other Questions</strong></a></li>
<li><a href="#Notes"><strong>Notes</strong></a></li>
</ul>
<p><a id="Polynomials_that_approach_a_Bernoulli_factory_function_fast"></a></p>
<h2 id="polynomials-that-approach-a-bernoulli-factory-function-fast">Polynomials that approach a Bernoulli factory function “fast”</h2>
<p>This question involves solving the Bernoulli factory problem with polynomials.<sup id="fnref:1"><a href="#fn:1" class="footnote" rel="footnote" role="doc-noteref">1</a></sup></p>
<p>In this question, a polynomial $P(x)$ is written in <em>Bernstein form of degree $n$</em> if it is written as—</p>
\[P(x)=\sum_{k=0}^n a_k {n \choose k} x^k (1-x)^{n-k},\]
<p>where the real numbers $a_0, …, a_n$ are the polynomial’s <em>Bernstein coefficients</em>.</p>
<p>The degree-$n$ <em>Bernstein polynomial</em> of an arbitrary function $f(x)$ has Bernstein coefficients $a_k = f(k/n)$. In general, this Bernstein polynomial differs from $f$ even if $f$ is a polynomial.</p>
<p><a id="Main_Question"></a></p>
<h3 id="main-question">Main Question</h3>
<p>Suppose $f:[0,1]\to [0,1]$ is continuous and belongs to a large class of functions (for example, the $k$-th derivative, $k\ge 0$, is continuous, Lipschitz continuous, concave, strictly increasing, or bounded variation, or $f$ is real analytic).</p>
<ol>
<li>(<em>Exact Bernoulli factory</em>): Compute the Bernstein coefficients of a sequence of polynomials ($g_n$) of degree 2, 4, 8, …, $2^i$, … that converge to $f$ from below and satisfy: $(g_{2n}-g_{n})$ is a polynomial with nonnegative Bernstein coefficients once it’s rewritten to a polynomial in Bernstein form of degree exactly $2n$. Assume $0\lt f(\lambda)\lt 1$ or a piecewise polynomial can come between $f$ or $1-f$ and the x-axis.</li>
<li>(<em>Approximate Bernoulli factory</em>): Given $\epsilon > 0$, compute the Bernstein coefficients of a polynomial or rational function (of some degree $n$) that is within $\epsilon$ of $f$.</li>
<li>(<em>Series expansion of simple functions</em>): Find a nonnegative random variable $X$ and a series $f(\lambda)=\sum_{a\ge 0}\gamma_a(\lambda)$ such that $\gamma_a(\lambda)/\mathbb{P}(X=a)$ (letting 0/0 equal 0) is a polynomial or rational function with rational Bernstein coefficients lying in $[0, 1]$.<sup id="fnref:2"><a href="#fn:2" class="footnote" rel="footnote" role="doc-noteref">2</a></sup> Do the same for a function that is within $\epsilon$ of $f$, rather than $f$.</li>
</ol>
<p>The convergence rate must be $O(1/n^{r/2})$ if the class has only functions with Lipschitz-continuous $(r-1)$-th derivative. The method may not introduce transcendental or trigonometric functions (as with Chebyshev interpolants).</p>
<p><a id="Solving_the_Bernoulli_factory_problem_with_polynomials"></a></p>
<h3 id="solving-the-bernoulli-factory-problem-with-polynomials">Solving the Bernoulli factory problem with polynomials</h3>
<p>An <a href="https://peteroupc.github.io/bernoulli.html#General_Factory_Functions"><strong>algorithm</strong></a> (Łatuszyński et al. 2009/2011)<sup id="fnref:3"><a href="#fn:3" class="footnote" rel="footnote" role="doc-noteref">3</a></sup> simulates a function that admits a Bernoulli factory $f(\lambda)$ via two sequences of polynomials that converge from above and below to that function. Roughly speaking, the algorithm works as follows:</p>
<ol>
<li>Generate U, a uniform random variate in $[0, 1]$.</li>
<li>Flip the input coin (with a probability of heads of $\lambda$), then build an upper and lower bound for $f(\lambda)$, based on the outcomes of the flips so far. In this case, these bounds come from two degree-$n$ polynomials that approach $f$ as $n$ gets large, where $n$ is the number of coin flips so far in the algorithm.</li>
<li>If U is less than or equal to the lower bound, return 1. If U is greater than the upper bound, return 0. Otherwise, go to step 2.</li>
</ol>
<p>The result of the algorithm is 1 with probability <em>exactly</em> equal to $f(\lambda)$, or 0 otherwise.</p>
<p>However, the algorithm requires the polynomial sequences to meet certain requirements, one of which is:</p>
<p><em>For $f(\lambda)$ there must be a sequence of polynomials</em> ($g_n$) <em>in Bernstein form of degree 1, 2, 3, … that converge to $f$ from below and satisfy:</em> $(g_{n+1}-g_{n})$ <em>is a polynomial with nonnegative Bernstein coefficients once it’s rewritten to a polynomial in Bernstein form of degree exactly $n+1$ (Nacu and Peres (2005)<sup id="fnref:4"><a href="#fn:4" class="footnote" rel="footnote" role="doc-noteref">4</a></sup>; Holtz et al. (2011)<sup id="fnref:5"><a href="#fn:5" class="footnote" rel="footnote" role="doc-noteref">5</a></sup>).<sup id="fnref:6"><a href="#fn:6" class="footnote" rel="footnote" role="doc-noteref">6</a></sup> For $f(\lambda)=1-f(\lambda)$ there must likewise be a sequence of this kind.</em></p>
<p><a id="A_Matter_of_Efficiency"></a></p>
<h3 id="a-matter-of-efficiency">A Matter of Efficiency</h3>
<p>However, ordinary Bernstein polynomials converge to a function at the rate $\Omega(1/n)$ unless the function is linear, a result known since Voronovskaya (1932)<sup id="fnref:7"><a href="#fn:7" class="footnote" rel="footnote" role="doc-noteref">7</a></sup> and a rate that will lead to an <strong>infinite expected number of coin flips in general</strong>. (See also my <a href="https://peteroupc.github.io/bernsupp.html"><strong>supplemental notes</strong></a>.)</p>
<p>But Lorentz (1966)<sup id="fnref:8"><a href="#fn:8" class="footnote" rel="footnote" role="doc-noteref">8</a></sup> showed that if the function is positive and has a continuous $k$-th derivative, there are polynomials with nonnegative Bernstein coefficients that converge at the rate $O(1/n^{k/2})$ (and thus can enable a <strong>finite expected number of coin flips</strong> if the function is “smooth” enough).</p>
<p>Thus, researchers have studied alternatives to Bernstein polynomials that improve the convergence rate for “smoother” functions. See Holtz et al. (2011)<sup id="fnref:5:1"><a href="#fn:5" class="footnote" rel="footnote" role="doc-noteref">5</a></sup>, Sevy (1991)<sup id="fnref:9"><a href="#fn:9" class="footnote" rel="footnote" role="doc-noteref">9</a></sup>, Waldron (2009)<sup id="fnref:10"><a href="#fn:10" class="footnote" rel="footnote" role="doc-noteref">10</a></sup>, Costabile et al. (2005)<sup id="fnref:11"><a href="#fn:11" class="footnote" rel="footnote" role="doc-noteref">11</a></sup>, Han (2003)<sup id="fnref:12"><a href="#fn:12" class="footnote" rel="footnote" role="doc-noteref">12</a></sup>, Khosravian-Arab et al. (2018)<sup id="fnref:13"><a href="#fn:13" class="footnote" rel="footnote" role="doc-noteref">13</a></sup>, and references therein; see also Micchelli (1973)<sup id="fnref:14"><a href="#fn:14" class="footnote" rel="footnote" role="doc-noteref">14</a></sup>, Güntürk and Li (2021a)<sup id="fnref:15"><a href="#fn:15" class="footnote" rel="footnote" role="doc-noteref">15</a></sup>, (2021b)<sup id="fnref:16"><a href="#fn:16" class="footnote" rel="footnote" role="doc-noteref">16</a></sup>, Draganov (2024)<sup id="fnref:17"><a href="#fn:17" class="footnote" rel="footnote" role="doc-noteref">17</a></sup>, and Tachev (2022)<sup id="fnref:18"><a href="#fn:18" class="footnote" rel="footnote" role="doc-noteref">18</a></sup>.</p>
<p>These alternative polynomials usually come with results where the error bound is the desired $O(1/n^{k/2})$, but most of those results (with the notable exception of Sevy) have hidden constants with no upper bounds given, making them unimplementable (that is, it can’t be known beforehand whether a given polynomial will come close to the target function within a user-specified error tolerance).</p>
<p><a id="A_Conjecture_on_Polynomial_Approximation"></a></p>
<h3 id="a-conjecture-on-polynomial-approximation">A Conjecture on Polynomial Approximation</h3>
<p>The following is a <a href="https://peteroupc.github.io/bernsupp.html#A_Conjecture_on_Polynomial_Approximation"><strong>conjecture</strong></a> that could help reduce this problem to the problem of finding explicit error bounds when approximating a function by polynomials.</p>
<p>Let $f(\lambda):[0,1]\to(0,1)$ have a continuous $r$-th derivative, where $r\ge 1$, let $M$ be the maximum of the absolute value of $f$ and its derivatives up to the $r$-th derivative, and denote the Bernstein polynomial of degree $n$ of a function $g$ as $B_n(g)$. Let $W_{2^0}(g; \lambda), W_{2^1}(g; \lambda), …, W_{2^i}(g; \lambda),…$ be a sequence of operators that map a continuous function $g$ on $[0, 1]$ to a bounded function on $[0, 1]$ and converge uniformly to $f$.</p>
<p>For each integer $n\ge 1$ that’s a power of 2, suppose that there is $D>0$ such that—</p>
\[\text{abs}(f(\lambda)-B_n(W_n(f; \lambda); \lambda)) \le DM/n^{r/2},\]
<p>whenever $0\le \lambda\le 1$. Then there is $C_0\ge D$ such that the polynomials $(g_n)$ in Bernstein form of degree 2, 4, 8, …, $2^i$, …, defined as $g_n=B_n(W_n(f; \lambda); \lambda) - C_0 M/n^{r/2}$, converge from below to $f$ and satisfy: $(g_{2n}-g_{n})$ is a polynomial with nonnegative Bernstein coefficients once it’s rewritten to a polynomial in Bernstein form of degree exactly $2n$.</p>
<p>Equivalently (see also Nacu and Peres (2005)<sup id="fnref:4:1"><a href="#fn:4" class="footnote" rel="footnote" role="doc-noteref">4</a></sup>), there is $C_1>0$ such that the inequality—</p>
\[W_{2n}\left(f; \frac{k}{2n}\right) + C_1 M/n^{r/2} - \sum_{i=0}^k W_n\left(f; \frac{i}{n}\right)\sigma_{n,k,i}\ge 0,\tag{PB}\]
<p>holds true for each integer $n\ge 1$ that’s a power of 2 and whenever $0\le k\le 2n$, where $\sigma_{n,k,i} = {n\choose i}{n\choose {k-i}}/{2n \choose k}=\mathbb{P}(X_k=i)$ and $X_k$ is a hypergeometric($2n$, $k$, $n$) random variable.</p>
<p>$C_0$ or $C_1$ may depend on $r$ and the sequence $W_n$, but not on $f$, $\lambda$, or $n$. When $C_0$ or $C_1$ exists, find a good upper bound for it.</p>
<blockquote>
<p><strong>Note:</strong> This conjecture may be easy to prove if $W_n$ reproduces polynomials of degree $(r-1)$ or less. But there are $B_n(W_n)$ (notably the iterated Boolean sum of Bernstein polynomials) that don’t do so and yet converge at the rate $O(n^{-r/2})$ for some $r\gt 2$. <strong>Also, see notes 3 and 4 in</strong> “<a href="#End_Notes"><strong>End Notes</strong></a>”.</p>
<p><strong>Note:</strong> I believe there is a counterexample to this conjecture, namely the sequence $B_n(W_n(f; \lambda); \lambda)=\frac{(T_n(1-2\lambda)+1)\varphi_n}{2 \mu_n} + 1/2$, where $\varphi_n$ is a decreasing sequence of positive numbers that tends slowly enough to 0, $\mu_n$ is the maximum Bernstein coefficient (in absolute value) of the degree-$n$ polynomial $(T_n(1-2\lambda)+1)/2$, and $T_n(x)$ is the Chebyshev polynomial of the first kind of degree $n$. If this counterexample is valid, the conjecture may still be true with an additional assumption on the convergence rate of $W_n$, say, $O(1/n)$ or $O(1/n^{r/2})$ or $O(1/n^{(r-1)/2})$.</p>
</blockquote>
<p><a id="Strategies"></a></p>
<h3 id="strategies">Strategies</h3>
<p>The following are some strategies for answering these questions:</p>
<ul>
<li>Verify my proofs for the results on error bounds for certain polynomials in “<a href="https://peteroupc.github.io/bernapprox.html#Results_Used_in_Approximations_by_Polynomials"><strong>Results Used in Approximations By Polynomials</strong></a>”, including:
<ul>
<li>Iterated Boolean sums (linear combinations of iterates) of Bernstein polynomials ($B_n(W_n) = f-(f-B_n(f))^k$:<sup id="fnref:19"><a href="#fn:19" class="footnote" rel="footnote" role="doc-noteref">19</a></sup> Propositions B10C and B10D.</li>
<li>Linear combinations of Bernstein polynomials (see Costabile et al. (2005)<sup id="fnref:11:1"><a href="#fn:11" class="footnote" rel="footnote" role="doc-noteref">11</a></sup>): Proposition B10.</li>
<li>The <a href="https://link.springer.com/article/10.1007/s00365-010-9108-5"><strong>Lorentz operator</strong></a> (Holtz et al. 2011)<sup id="fnref:5:2"><a href="#fn:5" class="footnote" rel="footnote" role="doc-noteref">5</a></sup>.</li>
</ul>
</li>
<li>Find the hidden constants $\theta_\alpha$, $s$, and $D$ as well as those in Lemmas 15, 17 to 22, 24, and 25 in Holtz et al. (2011)<sup id="fnref:5:3"><a href="#fn:5" class="footnote" rel="footnote" role="doc-noteref">5</a></sup>.</li>
<li>Find polynomials of the following kinds and find explicit bounds, with no hidden constants, on the approximation error for those polynomials:
<ul>
<li>Operators that produce a degree-$n$ polynomial in Bernstein form, or a ratio of two such polynomials, such that—
<ul>
<li>the operator preserves polynomials at a higher degree than linear functions, or</li>
<li>$O(n^2)$ sample points are required.</li>
</ul>
</li>
<li>Polynomials built from samples at <em>rational</em> values of a function $f$ that cluster at a quadratic rate toward the endpoints (Adcock et al. 2019)<sup id="fnref:20"><a href="#fn:20" class="footnote" rel="footnote" role="doc-noteref">20</a></sup> (for example, values that converge to Chebyshev points $\cos(j\pi/n)$ with increasing $n$, or to Legendre points). See also 7, 8, and 12 of Trefethen, <a href="https://www.chebfun.org/ATAP/"><strong><em>Approximation Theory and Approximation Practice</em></strong></a>, 2013.</li>
</ul>
</li>
</ul>
<p><a id="Other_Questions"></a></p>
<h2 id="other-questions">Other Questions</h2>
<ul>
<li>Let $f(\lambda):[0,1]\to [0,1]$ be writable as $f(\lambda)=\sum_{n\ge 0} a_n \lambda^n,$ where $a_n\ge 0$ is rational, $a_n$ is nonzero infinitely often, and $f(1)$ is irrational. Then what are simple criteria to determine whether there is $0\lt p\lt 1$ such that $0\le a_n\le p(1-p)^n$ and, if so, to find such $p$? Obviously, if $(a_n)$ is nowhere increasing then $1\gt p\ge a_0$.</li>
<li>For each $r>0$, characterize the functions $f(\lambda)$ that admit a Bernoulli factory where the expected number of coin flips, raised to the power of $r$, is finite.</li>
<li>
<p><a href="https://mathoverflow.net/questions/412772/from-biased-coins-to-biased-coins-as-efficiently-as-possible"><strong>Multiple-output Bernoulli factories</strong></a>: <strong>Let</strong> $f(\lambda):[a, b] \to (0, 1)$ <strong>be continuous, where</strong> $0\lt a$, $a\lt b$, $b\lt 1$. Define the entropy bound as $h(f(\lambda))/h(\lambda),$ where $h(x)=-x \ln(x)-(1-x) \ln(1-x)$ is related to the Shannon entropy function. Then there is an algorithm that tosses heads with probability $f(\lambda)$ given a coin that shows heads with probability $\lambda$ and no other source of randomness (Keane and O’Brien 1994)<sup id="fnref:21"><a href="#fn:21" class="footnote" rel="footnote" role="doc-noteref">21</a></sup>.</p>
<p>But, <strong>is there an algorithm for $f$ that produces multiple independent outputs rather than one and has an expected number of coin flips per output that is arbitrarily close to the entropy bound, uniformly for every $\lambda$ in $f$’s domain</strong>? Call such an algorithm an <em>optimal factory</em>. (See Nacu and Peres (2005, Question 1)<sup id="fnref:4:2"><a href="#fn:4" class="footnote" rel="footnote" role="doc-noteref">4</a></sup>.) And, does the answer change if the algorithm has access to a fair coin in addition to the biased coin?</p>
<p>So far, constants as well as $\lambda$ and $1-\lambda$ do admit an optimal factory (see same work), and, as Yuval Peres (Jun. 24, 2021) told me, there is an efficient multiple-output algorithm for $f(\lambda) = \lambda/2$. But are there others? See an <a href="https://peteroupc.github.io/bernsupp.html#Multiple_Output_Bernoulli_Factory"><strong>appendix in one of my articles</strong></a> for more information on my progress on the problem.</p>
</li>
<li>
<p><a href="https://cstheory.stackexchange.com/questions/50853/from-coin-flips-to-algebraic-functions-via-pushdown-automata"><strong>Pushdown automata and algebraic functions</strong></a>: A <em>pushdown automaton</em> is a finite state machine with an unbounded stack, driven by a biased coin with an unknown probability of heads, $\lambda$. Its stack starts with a single symbol. On each step, the machine flips the coin, then, based on the coin flip, the current state, and the top stack symbol, it moves to a new state (or keeps it unchanged) and replaces the top stack symbol with zero or more symbols. When the stack is empty, the machine stops and returns either 0 or 1 depending on the state it ends up at.</p>
<p>Let $f(\lambda)$ be continuous and map the open interval (0, 1) to itself. Mossel and Peres (2005)<sup id="fnref:22"><a href="#fn:22" class="footnote" rel="footnote" role="doc-noteref">22</a></sup> showed that a pushdown automaton can output 1 with probability $f(\lambda)$ only if $f$ is <em>algebraic over the rational numbers</em> (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$). See an <a href="https://peteroupc.github.io/bernsupp.html#Pushdown_Automata_and_Algebraic_Functions"><strong>appendix in one of my articles</strong></a> for more information on my progress on the problem.</p>
<p>Prove or disprove:</p>
<ol>
<li>If $f$ is algebraic over rational numbers it can be simulated by a pushdown automaton.</li>
<li>min($\lambda$, $1-\lambda$) and $\lambda^{1/p}$, for every prime $p\ge 3$, can be simulated by a pushdown automaton.</li>
<li>Given that $f$ is algebraic over rational numbers, it can be simulated by a pushdown automaton if and only if its “critical exponent” is a dyadic number greater than $-1$ or has the form $-1-1/2^k$ for some integer $k\ge 1$.<sup id="fnref:23"><a href="#fn:23" class="footnote" rel="footnote" role="doc-noteref">23</a></sup></li>
</ol>
</li>
<li><a href="https://mathoverflow.net/questions/448538/bounds-on-the-coin-flipping-degree"><strong>Coin-flipping degree</strong></a>: Let $p(\lambda)$ be a polynomial that maps the closed unit interval to itself and satisfies $0\lt p(\lambda)\lt 1$ whenever $0\lt\lambda\lt 1$. Then its <em>coin-flipping degree</em> (Wästlund 1999)<sup id="fnref:24"><a href="#fn:24" class="footnote" rel="footnote" role="doc-noteref">24</a></sup> is the smallest value of $n$ such that $p$’s <em>Bernstein</em> coefficients of degree $n$ lie in the closed unit interval. Given that a polynomial’s degree is $m$ and its “standard” coefficients are integers, what are upper bounds (or even exact maximums) on its coin flipping degree?</li>
<li><a href="https://stats.stackexchange.com/questions/541402/what-are-relatively-simple-simulations-that-succeed-with-an-irrational-probabili"><strong>Simple simulation algorithms</strong></a>: References are sought to papers and books that describe irrational constants or Bernoulli factory functions (continuous functions mapping (0,1) to itself) in any of the following ways. Ideally they should involve only rational numbers and should not compute <em>p</em>-adic digit expansions.
<ul>
<li>Simulation experiments that succeed with an irrational probability.</li>
<li>Simple <a href="https://peteroupc.github.io/bernoulli.html#Continued_Fractions"><strong>continued fraction</strong></a> expansions of irrational constants.</li>
<li>Functions written as infinite power series with rational coefficients (see “<a href="https://peteroupc.github.io/bernoulli.html#Certain_Power_Series"><strong>Certain Power Series</strong></a>”).</li>
<li>Irrational numbers written as series expansions with rational coefficients (see “<a href="https://peteroupc.github.io/bernoulli.html#Certain_Converging_Series"><strong>Certain Converging Series</strong></a>”).</li>
<li>Functions whose integral is an irrational number.</li>
<li>Closed shapes inside the unit square whose area is an irrational number. (Includes algorithms that tell whether a box lies inside, outside, or partly inside or outside the shape.) <a href="https://peteroupc.github.io/bernoulli.html#pi___4"><strong>Example.</strong></a></li>
<li>Generate a uniform (<em>x</em>, <em>y</em>) point inside a closed shape, then return 1 with probability <em>x</em>. For what shapes is the expected value of <em>x</em> an irrational number? <a href="https://peteroupc.github.io/bernsupp.html#4_3___pi"><strong>Example.</strong></a>.</li>
</ul>
</li>
<li>
<p>Given integer <em>m</em>≥0, rational number 0<<em>k</em><exp(1) (and especially $k=1$ or $k=2$), and unknown heads probability 0≤<em>λ</em>≤1, find a <a href="https://peteroupc.github.io/bernoulli.html"><strong>Bernoulli factory</strong></a> for—</p>
\[f(\lambda)=\exp(-(\exp(m+\lambda)-(k(m+\lambda)))) = \frac{\exp(-\exp(m+\lambda))}{\exp(-(k(m+\lambda)))},\tag{PD}\]
<p>that, as much as possible, avoids calculating $h(\lambda) = \exp(m+\lambda)-k(m+\lambda)$, and especially avoids floating-point operations; in this sense, the more implicitly the Bernoulli factory works with irrational or transcendental functions, the better. The right-hand side of (PD) can be implemented by <a href="https://peteroupc.github.io/bernoulli.html#ExpMinus_exp_minus__z"><strong>ExpMinus</strong></a> and division Bernoulli factories, but is inefficient and heavyweight due to the need to calculate $\epsilon$ for the division factory. In addition there is a Bernoulli factory that first calculates $h(\lambda)$ and $floor(h(\lambda))$ using constructive reals and then runs <strong>ExpMinus</strong>, but this is likewise far from lightweight.</p>
</li>
</ul>
<p>Prove or disprove:</p>
<ul>
<li>Given that $f:[0,1]\to (0,1]$ is convex, the polynomials $(g_n) = (B_n(f) - \max_{0\le\lambda\le 1}\text{abs}(B_n(f)(\lambda)-f(\lambda)))$ (where $n$ is a positive integer power of 2) are in Bernstein form of degree $n$, converge to $f$ from below, and satisfy: $(g_{2n}-g_{n})$ is a polynomial with nonnegative Bernstein coefficients once it’s rewritten to a polynomial in Bernstein form of degree exactly $2n$. The same is true for the polynomials $(g_n) = (B_n(f) - \text{abs}(B_n(f)(1/2)-f(1/2)))$, if $f$ is also symmetric about 1/2.</li>
<li>
<p>Let $f:(D\subseteq [0, 1])\to [0,1]$. Given a coin that shows heads with probability $\lambda$ (which can be 0 or 1), it is possible to toss heads with probability $f(\lambda)$ using the coin and no other sources of randomness (and, thus, $f$ is <a href="https://mathoverflow.net/questions/404961/from-biased-coins-and-nothing-else-to-biased-coins"><strong><em>strongly simulable</em></strong></a>) <strong>if and only if</strong>—</p>
<ul>
<li>$f$ is constant on its domain, or is continuous and polynomially bounded on its domain (<em>polynomially bounded</em> means, both $f$ and $1-f$ are bounded below by min($x^n$, $(1-x)^n$) for some integer $n$ (Keane and O’Brien 1994)<sup id="fnref:21:1"><a href="#fn:21" class="footnote" rel="footnote" role="doc-noteref">21</a></sup>), and</li>
<li>$f(0)$ is 0 or 1 if 0 is in $f$’s domain and $f(1)$ is 0 or 1 whenever 1 is in $f$’s domain, and</li>
<li>if $f(0) = 0$ or $f(1) = 0$ or both, then there is a polynomial $g(x):[0,1]\to [0,1]$ with computable coefficients, such that $g(0) = f(0)$ and $g(1) = f(1)$ whenever 0 or 1, respectively, is in the domain of f, and such that $g(x)\gt f(x)$ for every $x$ in the domain of $f$, except at 0 and 1, and</li>
<li>if $f(0) = 1$ or $f(1) = 1$ or both, then there is a polynomial $h(x):[0,1]\to [0,1]$ with computable coefficients, such that $h(0) = f(0)$ and $h(1) = f(1)$ whenever 0 or 1, respectively, is in the domain of $f$, and such that $h(x)\lt f(x)$ for every $x$ in the domain of f, except at 0 and 1.</li>
</ul>
<p>A condition such as “0 is not in the domain of $f$, or $f$ can be extended to a Lipschitz-continuous function on $[0, \epsilon)$ for some $\epsilon>0$” does not work. A counterexample is $f(x)=(\sin(1/x)/4+1/2)\cdot(1-(1-x)^n)$ for $n\ge 1$ ($f(0)=0$), which is strongly simulable at 0 despite not being Lipschitz at 0. ($(1-x)^n$ is the probability of the biased coin showing zero $n$ times in a row.) Keane and O’Brien already showed strong simulability when $D$ contains neither 0 nor 1.</p>
</li>
</ul>
<p><a id="Notes"></a></p>
<h2 id="notes">Notes</h2>
<div class="footnotes" role="doc-endnotes">
<ol>
<li id="fn:1">
<p>See also the following questions on <em>Mathematics Stack Exchange</em> and <em>MathOverflow</em>: <a href="https://math.stackexchange.com/questions/3904732/what-are-ways-to-compute-polynomials-that-converge-from-above-and-below-to-a-con"><strong>Converging polynomials</strong></a>, <a href="https://mathoverflow.net/questions/442057/explicit-and-fast-error-bounds-for-approximating-continuous-functions"><strong>Error bounds</strong></a>, <a href="https://mathoverflow.net/questions/427595/a-conjecture-on-consistent-monotone-sequences-of-polynomials-in-bernstein-form"><strong>A conjecture</strong></a>, <a href="https://mathoverflow.net/questions/407179/using-the-holtz-method-to-build-polynomials-that-converge-to-a-continuous-functi"><strong>Lorentz operators</strong></a>, <a href="https://mathoverflow.net/questions/409174/concave-functions-series-representation-and-converging-polynomials"><strong>Series representations</strong></a>. <a href="#fnref:1" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:2">
<p>An example of $X$ is $\mathbb{P}(X=a) = p (1-p)^a$ where $0 < p < 1$ is a known rational. This question’s requirements imply that $\sum_{a\ge 0}\max_\lambda \text{abs}(\gamma_a(\lambda)) \le 1$. The proof of Keane and O’Brien (1994) produces a convex combination of polynomials with 0 and 1 as Bernstein coefficients, but the combination is difficult to construct (it requires finding maximums, for example) and so this proof does not appropriately answer this question. <a href="#fnref:2" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:3">
<p>Łatuszyński, K., Kosmidis, I., Papaspiliopoulos, O., Roberts, G.O., “<a href="https://arxiv.org/abs/0907.4018v2"><strong>Simulating events of unknown probabilities via reverse time martingales</strong></a>”, arXiv:0907.4018v2 [stat.CO], 2009/2011. <a href="#fnref:3" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:4">
<p>Nacu, Şerban, and Yuval Peres. “Fast simulation of new coins from old”, The Annals of Applied Probability 15, no. 1A (2005): 93-115. <a href="#fnref:4" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:4:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a> <a href="#fnref:4:2" class="reversefootnote" role="doc-backlink">↩<sup>3</sup></a></p>
</li>
<li id="fn:5">
<p>Holtz, O., Nazarov, F., Peres, Y., “<a href="https://link.springer.com/article/10.1007/s00365-010-9108-5"><strong>New Coins from Old, Smoothly</strong></a>”, Constructive Approximation 33 (2011). <a href="#fnref:5" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:5:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a> <a href="#fnref:5:2" class="reversefootnote" role="doc-backlink">↩<sup>3</sup></a> <a href="#fnref:5:3" class="reversefootnote" role="doc-backlink">↩<sup>4</sup></a></p>
</li>
<li id="fn:6">
<p>The condition on nonnegative Bernstein coefficients ensures that not only the polynomials “increase” to $f(\lambda)$, but also their Bernstein coefficients. This condition is equivalent in practice to the following statement (Nacu & Peres 2005). For every integer $n\ge 1$ that’s a power of 2, $a(2n, k)\ge\mathbb{E}[a(n, X_{n,k})]= \left(\sum_{i=0}^k a(n,i) {n\choose i}{n\choose {k-i}}/{2n\choose k}\right)$, where $a(n,k)$ is the degree-$n$ polynomial’s $k$-th Bernstein coefficient, where $0\le k\le 2n$ is an integer, and where $X_{n,k}$ is a hypergeometric($2n$, $k$, $n$) random variable. A hypergeometric($2n$, $k$, $n$) random variable is the number of “good” balls out of $k$ balls taken uniformly at random, all at once, from a bag containing $2n$ balls, $n$ of which are “good”. See also my <a href="https://mathoverflow.net/questions/429037/bounds-on-the-expectation-of-a-function-of-a-hypergeometric-random-variable"><strong>MathOverflow question</strong></a> on finding bounds for hypergeometric variables. <a href="#fnref:6" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:7">
<p>E. Voronovskaya, “Détermination de la forme asymptotique d’approximation des fonctions par les polynômes de M. Bernstein”, 1932. <a href="#fnref:7" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:8">
<p>G.G. Lorentz, “The degree of approximation by polynomials with positive coefficients”, 1966. <a href="#fnref:8" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:9">
<p>Sevy, J., “Acceleration of convergence of sequences of simultaneous approximants”, dissertation, Drexel University, 1991. <a href="#fnref:9" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:10">
<p>Waldron, S., “<a href="https://www.sciencedirect.com/science/article/pii/S0021904508001640"><strong>Increasing the polynomial reproduction of a quasi-interpolation operator</strong></a>”, Journal of Approximation Theory 161 (2009). <a href="#fnref:10" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:11">
<p>Costabile, F., Gualtieri, M.I., Serra, S., “Asymptotic expansion and extrapolation for Bernstein polynomials with applications”, BIT 36 (1996) <a href="#fnref:11" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:11:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a></p>
</li>
<li id="fn:12">
<p>Han, Xuli. “Multi-node higher order expansions of a function.” Journal of Approximation Theory 124.2 (2003): 242-253. <a href="https://doi.org/10.1016/j.jat.2003.08.001"><strong>https://doi.org/10.1016/j.jat.2003.08.001</strong></a> <a href="#fnref:12" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:13">
<p>Khosravian-Arab, Hassan, Mehdi Dehghan, and M. R. Eslahchi. “A new approach to improve the order of approximation of the Bernstein operators: theory and applications.” Numerical Algorithms 77 (2018): 111-150. <a href="#fnref:13" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:14">
<p>Micchelli, Charles. “<a href="https://www.sciencedirect.com/science/article/pii/0021904573900282"><strong>The saturation class and iterates of the Bernstein polynomials</strong></a>”, Journal of Approximation Theory 8, no. 1 (1973): 1-18. <a href="#fnref:14" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:15">
<p>Güntürk, C. Sinan, and Weilin Li. “<a href="https://arxiv.org/pdf/2112.09183"><strong>Approximation with one-bit polynomials in Bernstein form</strong></a>”, arXiv:2112.09183 (2021); Constructive Approximation, pp.1-30 (2022). <a href="#fnref:15" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:16">
<p>Güntürk, C. Sinan, and Weilin Li. “<a href="https://arxiv.org/abs/2112.09181"><strong>Approximation of functions with one-bit neural networks</strong></a>”, arXiv:2112.09181 (2021). <a href="#fnref:16" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:17">
<p>Draganov, B.R., “<a href="https://www.fmi.uni-sofia.bg/sites/default/files/dissertation_work_doctor_of_science/dissdsci_borislavdraganov.pdf"><strong>Simultaneous approximation by the Bernstein operator</strong></a>”, dissertation, Sofia University “St. Kliment Ohridski”, 2024. <a href="#fnref:17" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:18">
<p>Tachev, Gancho. “<a href="https://doi.org/10.3934/mfc.2022061"><strong>Linear combinations of two Bernstein polynomials</strong></a>”, <em>Mathematical Foundations of Computing</em>, 2022. <a href="#fnref:18" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:19">
<p>If $W_n(f; 0)=f(0)$ and $W_n(f; 1)=f(1)$ for every $n$, then the inequality $(PB)$ is automatically true when $k=0$ and $k=2n$, so that the statement has to be checked only for $0\lt k\lt 2n$. If, in addition, $W_n$ is symmetric about 1/2, so that $W_n(f; \lambda)=W_n(f; 1-\lambda)$ whenever $0\le \lambda\le 1$, then the statement has to be checked only for $0\lt k\le n$ (since the values $\sigma_{n,k,i} = {n\choose i}{n\choose {k-i}}/{2n \choose k}$ are symmetric in that they satisfy $\sigma_{n,k,i}=\sigma_{n,k,k-i}$).<br />Special cases for this question are if $W_n = 2 f - B_n(f)$ and $r$ is 3 or 4, or $W_n = B_n(B_n(f))+3(f-B_n(f))$ and $r$ is 5 or 6; these cases correspond to the iterated Boolean sum of Bernstein polynomials: $B_n(W_n)=f-(f-B_n(f))^k$, which don’t reproduce polynomials of higher degree than linear functions, making it hard to find a bound better than $O(1/n)$ that satisfies the conjecture when $r\ge 3$. <a href="#fnref:19" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:20">
<p>Adcock, B., Platte, R.B., Shadrin, A., “Optimal sampling rates for approximating analytic functions from pointwise samples, IMA Journal of Numerical Analysis 39(3), July 2019. <a href="#fnref:20" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:21">
<p>Keane, M. S., and O’Brien, G. L., “A Bernoulli factory”, <em>ACM Transactions on Modeling and Computer Simulation</em> 4(2), 1994. <a href="#fnref:21" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:21:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a></p>
</li>
<li id="fn:22">
<p>Mossel, Elchanan, and Yuval Peres. New coins from old: computing with unknown bias. Combinatorica, 25(6), pp.707-724, 2005. <a href="#fnref:22" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:23">
<p>On pushdown automata: Etessami and Yannakakis (“Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations”, <em>Journal of the ACM</em> 56(1), pp.1-66, 2009) showed that pushdown automata with rational probabilities are equivalent to recursive Markov chains (with rational transition probabilities), and that for every recursive Markov chain, the system of polynomial equations has nonnegative coefficients. But this paper doesn’t deal with the case of recursive Markov chains where the transition probabilities cannot just be rational, but can also be $\lambda$ and $1-\lambda$ where $\lambda$ is an unknown rational or irrational probability of heads. Also, Banderier and Drmota (“Formulae and asymptotics for coefficients of algebraic functions”, <em>Combinatorics, Probability and Computing</em> 24(1), pp.1-53., 2014) showed the asymptotic behavior of power series solutions $f(\lambda)$ of a polynomial system, where both the series and the system have nonnegative real coefficients. Notably, functions of the form $\lambda^{1/p}$ where $p\ge 3$ is not a power of 2, are not possible solutions, because their so-called “critical exponent” is not dyadic. But the result seems not to apply to <em>piecewise</em> power series such as $\min(\lambda,1-\lambda)$, which are likewise algebraic functions. <a href="#fnref:23" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:24">
<p>Wästlund, J., “<a href="http://www.math.chalmers.se/~wastlund/coinFlip.pdf"><strong>Functions arising by coin flipping</strong></a>”, 1999. <a href="#fnref:24" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
</ol>
</div>
</div><nav id="navigation"><ul>
<li><a href="/">Back to start site.</a>
<li><a href="https://github.com/peteroupc/peteroupc.github.io">This site's repository (source code)</a>
<li><a href="https://github.com/peteroupc/peteroupc.github.io/issues">Post an issue or comment</a></ul>
<div class="noprint">
<p>
<a href="//x.com/intent/post?text=Open+Questions+on+the+Bernoulli+Factory+Problem&url=https%3A%2F%2Fpeteroupc.github.io%2Fbernreq.html">Share via X (Twitter)</a>, <a href="//www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fpeteroupc.github.io%2Fbernreq.html">Share via Facebook</a>, <a href="//news.ycombinator.com/submitlink?u=https%3A%2F%2Fpeteroupc.github.io%2Fbernreq.html&t=Open+Questions+on+the+Bernoulli+Factory+Problem">Share via Hacker News</a>, <a href="//www.reddit.com/submit?url=https%3A%2F%2Fpeteroupc.github.io%2Fbernreq.html&title=Open+Questions+on+the+Bernoulli+Factory+Problem">Share via Reddit</a>
</p>
</div>
<p style='font-size:120%;font-weight:bold'><a href='https://peteroupc.github.io/bernreq.pdf'>Download a PDF of this page</a></p><p>Of interest to the computer graphics and music community:</p><ul><li><a href='https://peteroupc.github.io/graphics.html'><b>Graphics for classic-style game development</b></a>.<li><a href='https://peteroupc.github.io/graphics.html#Building_a_Public_Domain_music_synthesis_library_and_instrument_banks'><b>MIDI music synthesis for classic-style games and apps</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper'><b>Tileable wallpapers with limited colors and resolution</b></a>.<li><a href='https://peteroupc.github.io/graphicsapi.html'><b>Lean programming interfaces for classic graphics</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper/docs/uielements.html'><b>Traditional user-interface graphics</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper/docs/pixeltovector.html'><b>Converting images to vector graphics</b></a>.</ul><p>Open questions for math and probability experts:</p><ul><li><a href='https://peteroupc.github.io/requests.html'><b>Requests and open questions</b></a>.<li><a href='https://peteroupc.github.io/bernreq.html'><b>Open questions on the Bernoulli factory problem (the new-coins-from-old problem)</b></a>.<li><a href='https://peteroupc.github.io/requestsother.html'><b>Other open questions on probability</b></a>.<li><a href='https://peteroupc.github.io/sampling.html'><b>The sampling problem</b></a>.</ul></nav></body></html>