-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy pathbernreq.html
executable file
·293 lines (219 loc) · 41.3 KB
/
bernreq.html
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
<!DOCTYPE html><html xmlns:dc="http://purl.org/dc/terms/" itemscope itemtype="http://schema.org/Article"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><title>Open Questions on the Bernoulli Factory Problem</title><meta name="citation_title" content="Open Questions on the Bernoulli Factory Problem"><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_date" content="2025/02/01"><meta name="citation_online_date" content="2025/02/01"><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="twitter:title" content="Open Questions on the Bernoulli Factory Problem"><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><a href="mailto:[email protected]"><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 only for certain functions $f$. (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>Specifically, the only functions that can be simulated this way <strong>are continuous and polynomially bounded on their domain, and map $[0, 1]$ or a subset thereof to $[0, 1]$</strong>, as well as $f=0$ and $f=1$. These functions are called <em>factory functions</em> in this page. (A function $f(x)$ is <em>polynomially bounded</em> if both $f$ and $1-f$ are greater than or equal to min($x^n$, $(1-x)^n$) for some integer $n$ (Keane and O’Brien 1994)<sup id="fnref:1" role="doc-noteref"><a href="#fn:1" class="footnote" rel="footnote">1</a></sup>. This implies that $f$ admits no roots on (0, 1) and can’t take on the value 0 or 1 except possibly at 0, 1, or both.)</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_factory_function_fast"><strong>Polynomials that approach a 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="#End_Notes"><strong>End Notes</strong></a></li>
<li><a href="#Notes"><strong>Notes</strong></a></li>
</ul>
<p><a id="Polynomials_that_approach_a_factory_function_fast"></a></p>
<h2 id="polynomials-that-approach-a-factory-function-fast">Polynomials that approach a factory function “fast”</h2>
<p>This question involves solving the Bernoulli factory problem with polynomials.<sup id="fnref:2" role="doc-noteref"><a href="#fn:2" class="footnote" rel="footnote">2</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 $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$. (<strong>See Note 3 in “<a href="#End_Notes">**End Notes**</a>”.</strong>) Assume $0\lt f(\lambda)\lt 1$ or $f$ is polynomially bounded.</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]$. (<strong>See note 1 in “<a href="#End_Notes">**End Notes**</a>”.</strong>)</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" role="doc-noteref"><a href="#fn:3" class="footnote" rel="footnote">3</a></sup> simulates a factory function $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; among them, the sequences must be of Bernstein-form polynomials that converge from above and below to a factory function. Specifically:</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$ (<strong>see Note 3 in “<a href="#End_Notes">**End Notes**</a>“</strong>; Nacu and Peres (2005)<sup id="fnref:4" role="doc-noteref"><a href="#fn:4" class="footnote" rel="footnote">4</a></sup>; Holtz et al. (2011)<sup id="fnref:5" role="doc-noteref"><a href="#fn:5" class="footnote" rel="footnote">5</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)$ in general, a result known since Voronovskaya (1932)<sup id="fnref:6" role="doc-noteref"><a href="#fn:6" class="footnote" rel="footnote">6</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:7" role="doc-noteref"><a href="#fn:7" class="footnote" rel="footnote">7</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 developed alternatives, including linear combinations and iterated Boolean sums of Bernstein polynomials, to improve the convergence rate. These include Micchelli (1973)<sup id="fnref:8" role="doc-noteref"><a href="#fn:8" class="footnote" rel="footnote">8</a></sup>, Guan (2009)<sup id="fnref:9" role="doc-noteref"><a href="#fn:9" class="footnote" rel="footnote">9</a></sup>, Güntürk and Li (2021a)<sup id="fnref:10" role="doc-noteref"><a href="#fn:10" class="footnote" rel="footnote">10</a></sup>, (2021b)<sup id="fnref:11" role="doc-noteref"><a href="#fn:11" class="footnote" rel="footnote">11</a></sup>, the “Lorentz operator” in Holtz et al. (2011)<sup id="fnref:5:1" role="doc-noteref"><a href="#fn:5" class="footnote" rel="footnote">5</a></sup>, Draganov (2014), and Tachev (2022)<sup id="fnref:12" role="doc-noteref"><a href="#fn:12" class="footnote" rel="footnote">12</a></sup>.</p>
<p>These alternative polynomials usually include results where the error bound is the desired $O(1/n^{k/2})$, but most of those results (for example, Theorem 4.4 in Micchelli; Theorem 5 in Güntürk and Li) 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 $r\ge 1$ continuous derivatives, 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}(\lambda), W_{2^1}(\lambda), …, W_{2^i}(\lambda),…$ be a sequence of functions on [0, 1] that 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(\lambda))) \le DM/n^{r/2},\]
<p>whenever $0\le \lambda\le 1$. Then there is $C_0\ge D$ such that for every $C\ge C_0$, the polynomials $(g_n)$ in Bernstein form of degree 2, 4, 8, …, $2^i$, …, defined as $g_n=B_n(W_n(\lambda) - CM/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$. (<strong>See Note 3 in “<a href="#End_Notes">**End Notes**</a>”.</strong>)</p>
<p>Equivalently (see also Nacu and Peres (2005)<sup id="fnref:4:1" role="doc-noteref"><a href="#fn:4" class="footnote" rel="footnote">4</a></sup>), there is $C_1>0$ such that the inequality $(PB)$ (see later) holds true for each integer $n\ge 1$ that’s a power of 2 (see “Strategies”, later).</p>
<p>My goal is to see not just whether this conjecture is true, but also which value of $C_0$ (or $C_1$) suffices for the conjecture, especially for any combination of the special cases mentioned at the end of “<a href="#Main_Question"><strong>Main Question</strong></a>”, earlier.</p>
<p><a id="Strategies"></a></p>
<h3 id="strategies">Strategies</h3>
<p>The following are some strategies for answering these questions:</p>
<ul>
<li>For iterated Boolean sums (linear combinations of iterates) of Bernstein polynomials ($U_{n,k}$ in <a href="https://www.sciencedirect.com/science/article/pii/0021904573900282"><strong>Micchelli 1973</strong></a>; see also <a href="https://arxiv.org/abs/2112.09181"><strong>Güntürk and Li</strong></a>), verify my <a href="https://peteroupc.github.io/bernapprox.html#Results_Used_in_Approximations_by_Polynomials"><strong>proofs of these bounds in Propositions B10C and B10D</strong></a>.</li>
<li>For linear combinations of Bernstein polynomials (Butzer (1953)<sup id="fnref:13" role="doc-noteref"><a href="#fn:13" class="footnote" rel="footnote">13</a></sup>, <a href="https://doi.org/10.3934/mfc.2022061"><strong>Tachev 2022</strong></a>), verify my proof of those error bounds in <a href="https://peteroupc.github.io/bernapprox.html#Results_Used_in_Approximations_by_Polynomials"><strong>my Proposition B10</strong></a>.</li>
<li>For 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" role="doc-noteref"><a href="#fn:5" class="footnote" rel="footnote">5</a></sup>, find explicit bounds, with no hidden constants, on the approximation error for the operator $Q_{n,r}(f)$ and for the polynomials $(f_n)$ and $(g_n)$ formed with it, and find the hidden constants $\theta_\alpha$, $s$, and $D$ as well as those in Lemmas 15, 17 to 22, 24, and 25 in the paper. Or verify my proof of the order-2 operator’s error bounds in <a href="https://peteroupc.github.io/bernapprox.html#Results_Used_in_Approximations_by_Polynomials"><strong>my Proposition B10A</strong></a>. The bounds should have the form $C\cdot\max((\lambda(1-\lambda)/n)^{1/2}, 1/n)^r$, where $C$ is an explicitly given constant depending only on $f$ and $r$.</li>
<li>Let $f:[-1,1]\to [0,1]$ be continuous. Find explicit bounds, with no hidden constants, on the error in approximating $f$ with the following polynomials: The polynomials are similar to Chebyshev interpolants, but evaluate $f$ at <em>rational</em> values of $\lambda$ that converge to Chebyshev or Legendre points (for example, converging to $\cos(j\pi/n)$ with increasing $n$). The error bounds must be close to those of Chebyshev interpolants (see, for example, chapters 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>
<li>Find other polynomial operators meeting the requirements of the main question (see “Main Question”, earlier) and having explicit error bounds, with no hidden constants, especially operators that preserve polynomials of a higher degree than linear functions.</li>
<li>
<p>Find a sequence of functions $(W_n(f))$ and an explicit and tight upper bound on $C_1>0$ such that, for each integer $n\ge 1$ that’s a power of 2—</p>
\[\text{abs}\left(\left(\sum_{i=0}^k W_n\left(\frac{i}{n}\right)\sigma_{n,k,i}\right)-W_{2n}\left(\frac{k}{2n}\right)\right)=\text{abs}(\mathbb{E}[W_n(X_k/n)] - W_{2n}(\mathbb{E}[X_k/n]))\le \frac{C_1 M}{n^{r/2}},\tag{PB}\]
<p>whenever $0\le k\le 2n$, where $M = \max(L, \max\text{abs}(f^{(0)}), …,\max\text{abs}(f^{(r-1)}))$, $L$ is $\max\text{abs}(f^{(r)})$ or the Lipschitz constant of $f^{(r-1)}$, $X_k$ is a hypergeometric($2n$, $k$, $n$) random variable, and $\sigma_{n,k,i} = {n\choose i}{n\choose {k-i}}/{2n \choose k}=\mathbb{P}(X_k=i)$ is the probability that $X_k$ equals $i$. (<strong>See notes 3 and 4 in</strong> “<a href="#End_Notes"><strong>End Notes</strong></a>” <strong>as well as</strong> “<a href="https://peteroupc.github.io/bernsupp.html#Proofs_for_Polynomial_Building_Schemes"><strong>Proofs for Polynomial-Building Schemes</strong></a>”.)</p>
</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:1:1" role="doc-noteref"><a href="#fn:1" class="footnote" rel="footnote">1</a></sup>.</p>
<p>But, <strong>is there an algorithm for $f$ that produces <em>multiple</em> 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" role="doc-noteref"><a href="#fn:4" class="footnote" rel="footnote">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:14" role="doc-noteref"><a href="#fn:14" class="footnote" rel="footnote">14</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$. (<strong>See note 2 in</strong> <a href="#End_Notes"><strong>“End Notes”</strong></a><strong>.</strong>)</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:15" role="doc-noteref"><a href="#fn:15" class="footnote" rel="footnote">15</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 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)$; in this sense, the more implicitly the Bernoulli factory works with irrational or transcendental functions, the better. A solution is sought especially when <em>k</em> is 1 or 2. Note that 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. (Calculating exp(.) with floating-point operations is not acceptable for this question.)</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\ge 1$ is an 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:1:2" role="doc-noteref"><a href="#fn:1" class="footnote" rel="footnote">1</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 $g(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="End_Notes"></a></p>
<h2 id="end-notes">End Notes</h2>
<p><strong>Note 1</strong>: 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)<sup id="fnref:1:3" role="doc-noteref"><a href="#fn:1" class="footnote" rel="footnote">1</a></sup> 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.</p>
<p><strong>Note 2</strong>: On pushdown automata: Etessami and Yannakakis (2009)<sup id="fnref:16" role="doc-noteref"><a href="#fn:16" class="footnote" rel="footnote">16</a></sup> 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 (2014)<sup id="fnref:17" role="doc-noteref"><a href="#fn:17" class="footnote" rel="footnote">17</a></sup> 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.</p>
<p><strong>Note 3</strong>: This condition is also known as a “consistency requirement”; it 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)<sup id="fnref:4:3" role="doc-noteref"><a href="#fn:4" class="footnote" rel="footnote">4</a></sup>. 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 $n$ balls taken uniformly at random, all at once, from a bag containing $2n$ balls, $k$ 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.</p>
<p><strong>Note 4</strong>: If $W_n(0)=f(0)$ and $W_n(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(\lambda)=W_n(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 />This question is a problem of finding the <em>Jensen gap</em> of $W_n$ for certain kinds of hypergeometric random variables (<strong>see Note 3</strong>). Lee et al. (2021)<sup id="fnref:18" role="doc-noteref"><a href="#fn:18" class="footnote" rel="footnote">18</a></sup> deal with a problem very similar to this one and find results that take advantage of $f$’s (here, $W_n$’s) smoothness, but unfortunately assume the variable is supported on an <em>open</em> interval, rather than a <em>closed</em> one (namely $[0,1]$) as in this question.<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.<br />Particularly for the case $W_n=2f-B_n(f)$, the right-hand side of $(PB)$ is believed to be $O(1/n^{3/2})$ when $f$ has a Lipschitz continuous second derivative on $[0,1]$, but I have been unable to find a bound better than $O(1/n)$, especially because in one form or another my attempts at the bound seem to require an estimate of $\text{abs}(B_{2n}(f)-B_{n}(f))$, which in general is no better than $O(1/n)$. Thus, a proof or counterexample of a bound of $O(1/n^{3/2})$ in this case would be appreciated.</p>
<p><a id="Notes"></a></p>
<h2 id="notes">Notes</h2>
<div class="footnotes" role="doc-endnotes">
<ol>
<li id="fn:1" role="doc-endnote">
<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:1" class="reversefootnote" role="doc-backlink">↩</a> <a href="#fnref:1:1" class="reversefootnote" role="doc-backlink">↩<sup>2</sup></a> <a href="#fnref:1:2" class="reversefootnote" role="doc-backlink">↩<sup>3</sup></a> <a href="#fnref:1:3" class="reversefootnote" role="doc-backlink">↩<sup>4</sup></a></p>
</li>
<li id="fn:2" role="doc-endnote">
<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/429037/bounds-on-the-expectation-of-a-function-of-a-hypergeometric-random-variable"><strong>Hypergeometric random variable</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/447064/explicit-bounds-on-derivatives-of-moments-related-to-bernstein-polynomials"><strong>Derivatives of moments</strong></a>, <a href="https://mathoverflow.net/questions/409174/concave-functions-series-representation-and-converging-polynomials"><strong>Series representations</strong></a>. <a href="#fnref:2" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:3" role="doc-endnote">
<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" role="doc-endnote">
<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> <a href="#fnref:4:3" class="reversefootnote" role="doc-backlink">↩<sup>4</sup></a></p>
</li>
<li id="fn:5" role="doc-endnote">
<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></p>
</li>
<li id="fn:6" role="doc-endnote">
<p>E. Voronovskaya, “Détermination de la forme asymptotique d’approximation des fonctions par les polynômes de M. Bernstein”, 1932. <a href="#fnref:6" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:7" role="doc-endnote">
<p>G.G. Lorentz, “The degree of approximation by polynomials with positive coefficients”, 1966. <a href="#fnref:7" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:8" role="doc-endnote">
<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:8" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:9" role="doc-endnote">
<p>Guan, Zhong. “<a href="https://arxiv.org/pdf/0909.0684"><strong>Iterated Bernstein polynomial approximations</strong></a>.” arXiv preprint arXiv:0909.0684 (2009). <a href="#fnref:9" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:10" role="doc-endnote">
<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:10" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:11" role="doc-endnote">
<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:11" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:12" role="doc-endnote">
<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:12" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:13" role="doc-endnote">
<p>Butzer, P.L., “Linear combinations of Bernstein polynomials”, Canadian Journal of Mathematics 15 (1953). <a href="#fnref:13" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:14" role="doc-endnote">
<p>Mossel, Elchanan, and Yuval Peres. New coins from old: computing with unknown bias. Combinatorica, 25(6), pp.707-724, 2005. <a href="#fnref:14" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:15" role="doc-endnote">
<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:15" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:16" role="doc-endnote">
<p>Etessami, K. And Yannakakis, M., “Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations”, Journal of the ACM 56(1), pp.1-66, 2009. <a href="#fnref:16" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:17" role="doc-endnote">
<p>Banderier, C. And Drmota, M., 2015. Formulae and asymptotics for coefficients of algebraic functions. Combinatorics, Probability and Computing, 24(1), pp.1-53. <a href="#fnref:17" class="reversefootnote" role="doc-backlink">↩</a></p>
</li>
<li id="fn:18" role="doc-endnote">
<p>Lee, Sang Kyu, Jae Ho Chang, and Hyoung-Moon Kim. “Further sharpening of Jensen’s inequality.” Statistics 55, no. 5 (2021): 1154-1168. <a href="#fnref:18" 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="//twitter.com/intent/tweet">Share via Twitter</a>, <a href="//www.facebook.com/sharer/sharer.php" id="sharer">Share via Facebook</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></nav></body></html>