-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy pathrequestsother.html
executable file
·382 lines (277 loc) · 30 KB
/
requestsother.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
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
<!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"><meta name="citation_pdf_url" content="https://peteroupc.github.io/requestsother.pdf"><meta name="citation_url" content="https://peteroupc.github.io/requestsother.html"><meta name="citation_date" content="2024/12/24"><meta name="citation_online_date" content="2024/12/24"><meta name="og:type" content="article"><meta name="og:url" content="https://peteroupc.github.io/requestsother.html"><meta name="og:site_name" content="peteroupc.github.io"><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="other-open-questions-on-probability">Other Open Questions on Probability</h1>
<p>This page lists certain open questions on probability. Any answers to these questions will greatly improve my articles posted on this site. 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>
<p><a id="Contents"></a></p>
<h2 id="contents">Contents</h2>
<ul>
<li><a href="#Contents"><strong>Contents</strong></a></li>
<li><a href="#Additional_Requests_and_Open_Questions"><strong>Additional Requests and Open Questions</strong></a></li>
<li><a href="#Probability_distributions_computable_by_pushdown_automata"><strong>Probability distributions computable by pushdown automata</strong></a>
<ul>
<li><a href="#Pushdown_Generators"><strong>Pushdown Generators</strong></a></li>
<li><a href="#Distributions_Computable_by_Pushdown_Generators"><strong>Distributions Computable by Pushdown Generators</strong></a></li>
<li><a href="#Questions"><strong>Questions</strong></a></li>
</ul>
</li>
<li><a href="#Checking_if_a_shape_covers_a_box"><strong>Checking if a shape covers a box</strong></a>
<ul>
<li><a href="#Questions_2"><strong>Questions</strong></a></li>
<li><a href="#Examples"><strong>Examples</strong></a></li>
</ul>
</li>
<li><a href="#Probabilities_arising_from_permutations"><strong>Probabilities arising from permutations</strong></a>
<ul>
<li><a href="#Questions_3"><strong>Questions</strong></a></li>
</ul>
</li>
<li><a href="#Questions_on_Estimation_Algorithms"><strong>Questions on Estimation Algorithms</strong></a></li>
<li><a href="#References"><strong>References</strong></a></li>
<li><a href="#License"><strong>License</strong></a></li>
</ul>
<p><a id="Additional_Requests_and_Open_Questions"></a></p>
<h2 id="additional-requests-and-open-questions">Additional Requests and Open Questions</h2>
<p>Besides the requests and open questions found here, the following pages list others:</p>
<ul>
<li><a href="https://peteroupc.github.io/bernreq.html"><strong>Open Questions on the Bernoulli Factory Problem</strong></a></li>
<li><a href="https://peteroupc.github.io/requests.html"><strong>Requests and Open Questions</strong></a></li>
</ul>
<p><a id="Probability_distributions_computable_by_pushdown_automata"></a></p>
<h2 id="probability-distributions-computable-by-pushdown-automata">Probability distributions computable by pushdown automata</h2>
<p><a href="https://cstheory.stackexchange.com/questions/50826/probability-distributions-generated-by-pushdown-automata"><strong>https://cstheory.stackexchange.com/questions/50826/probability-distributions-generated-by-pushdown-automata</strong></a></p>
<p>This question is about generating random variates, in the form of their binary expansions, on restricted computing models. Specifically, the computing model is based on <em>pushdown automata</em> (finite-state machines with a stack) that are driven by flips of a coin and generate the binary expansion of a real number. This results in machines called <em>pushdown generators</em>, defined next.</p>
<p><a id="Pushdown_Generators"></a></p>
<h3 id="pushdown-generators">Pushdown Generators</h3>
<p>A <em>pushdown generator</em> has a finite set of <em>states</em> and a finite set of <em>stack symbols</em>, one of which is called EMPTY, and takes either a fair coin or a coin whose probability of heads is unknown. It starts with a given state and its stack starts with EMPTY. On each iteration:</p>
<ul>
<li>The automaton flips the coin.</li>
<li>Based on the coin flip (HEADS or TAILS), the current state, and the top stack symbol, it moves to a new state (or keeps it unchanged), replaces the top stack symbol with zero, one, or two symbols, and <em>optionally</em> gives out a base-N digit. Thus, there are three kinds of <em>transition rules</em>:
<ul>
<li>(<em>state</em>, <em>flip</em>, <em>symbol</em>) → (<em>digit</em>, <em>state2</em>, {<em>symbol2</em>}): move to <em>state2</em>, write <em>digit</em>, replace top stack symbol with same or different one.</li>
<li>(<em>state</em>, <em>flip</em>, <em>symbol</em>) → (<em>digit</em>, <em>state2</em>, {<em>symbol2</em>, <em>new</em>}): move to <em>state2</em>, write <em>digit</em>, replace top stack symbol with <em>symbol2</em>, then <em>push</em> a new symbol (<em>new</em>) onto the stack.</li>
<li>(<em>state</em>, <em>flip</em>, <em>symbol</em>) → (<em>digit</em>, <em>state2</em>, {}): move to <em>state2</em>, write <em>digit</em>, <em>pop</em> the top symbol from the stack.</li>
</ul>
</li>
</ul>
<p>In the transition rules above, <em>digit</em> is either a base-N digit or the empty string. Also, the machine terminates with probability 0, and rules that would cause the stack to be empty are not allowed. The infinite “output” of the machine is a real number $X$ in the interval [0, 1], in the form of the base-N digit expansion <code>0.dddddd...</code>, where <code>dddddd...</code> are the digits produced by the machine from left to right.</p>
<p>See also Yao 1985.</p>
<p>A <em>finite-state generator</em> (Knuth and Yao 1976) is the special case of a pushdown generator where the probability of heads is 1/2, each digit is either 0 or 1, rules can’t push stack symbols, and only one stack symbol is used. (In other words, a finite-state generator is a <em>finite automaton</em> driven by fair coin flips.)</p>
<p><a id="Distributions_Computable_by_Pushdown_Generators"></a></p>
<h3 id="distributions-computable-by-pushdown-generators">Distributions Computable by Pushdown Generators</h3>
<p>The question that interests me is which probability distributions of real numbers can be computed by pushdown generators, and how they can be constructed.</p>
<p>For example, a pushdown generator with a loop that outputs 0 or 1 at an equal chance produces a <em>uniform distribution</em>.</p>
<p>In this sense, there are existing results for finite-state generators. For example:</p>
<ul>
<li>Let $X$ be the random variable computable by a finite-state generator, and let $PDF(x)$ be the probability density function of $X$. Then if $PDF(x)$ is infinitely differentiable on the open interval (0, 1), it must be a polynomial with rational coefficients and not equal 0 at any irrational point on (0, 1) (Kindler and Romik 2004).</li>
</ul>
<p>Also, I believe that the <a href="https://peteroupc.github.io/bernsupp.html#Finite_State_and_Pushdown_Generators"><strong>following results</strong></a> are true:</p>
<ol>
<li>Suppose a finite-state generator can generate a probability distribution that takes on finitely many values. Then: Each value occurs with a rational probability; and each value is either rational or transcendental. This belief is in view of the results of Adamczewski et al. 2020.</li>
<li>If the distribution function generated by a finite-state generator is continuous and algebraic on the open interval (0, 1), then that function is a piecewise polynomial function.</li>
</ol>
<p><a id="Questions"></a></p>
<h3 id="questions">Questions</h3>
<p>The first question is whether the two results at the end of the previous section are true.</p>
<p>The following questions ask what kinds of distributions are possible with these generators (both when the coin driving the generators is fair, and when it has an unknown probability):</p>
<ol>
<li>
<p>Of the probability distributions that a finite-state generator can generate, what is the exact class of:</p>
<ul>
<li>Discrete distributions (those that cover a finite or countably infinite set of values)?</li>
<li>Absolutely continuous distributions (those with a probability density function such as the uniform or triangular distribution)?</li>
<li>Singular distributions (covering an uncountable but measure-zero set)?</li>
<li>Absolutely continuous distributions with <em>continuous</em> density functions?</li>
</ul>
</li>
<li>
<p>Same question as 1, but for pushdown generators.</p>
</li>
<li>
<p>Of the probability distributions that a pushdown generator can generate, what is the exact class of distributions with piecewise density functions whose pieces are infinitely differentiable? (The answer is known for finite-state generators.)</p>
</li>
</ol>
<p><a id="Checking_if_a_shape_covers_a_box"></a></p>
<h2 id="checking-if-a-shape-covers-a-box">Checking if a shape covers a box</h2>
<p><a href="https://math.stackexchange.com/questions/3882545/what-conditions-ensure-that-checking-if-a-shape-covers-a-box-can-be-done-just-by"><strong>https://math.stackexchange.com/questions/3882545/what-conditions-ensure-that-checking-if-a-shape-covers-a-box-can-be-done-just-by</strong></a></p>
<p>I have described an <a href="https://peteroupc.github.io/exporand.html#Uniform_Distribution_Inside_N_Dimensional_Shapes"><strong>algorithm for generating random points inside an arbitrary shape</strong></a> (such as a circle, polygon, or an arbitrary closed curve) contained within a box. It involves checking whether the box is outside or partially or fully inside the shape, and then—</p>
<ul>
<li>generating a uniform random point inside the box if the box is inside the shape,</li>
<li>rejecting the box and starting over if the box is outside the shape, and</li>
<li>subdividing the box, choosing a random subbox, and repeating this process for that subbox otherwise.</li>
</ul>
<p>This algorithm uses a function called <strong>InShape</strong> that determines whether a shape covers an axis-aligned bounding box. It takes such a bounding box as input and returns—</p>
<ul>
<li><em>YES</em> if the box is entirely inside the shape;</li>
<li><em>NO</em> if the box is entirely outside the shape; and</li>
<li><em>MAYBE</em> if the box is partly inside and partly outside the shape.</li>
</ul>
<p>Now, take a particular implementation of <strong>InShape</strong> that has certain knowledge about a particular shape. Assume the following:</p>
<ul>
<li>The shape is closed, has nonzero finite volume, and has a boundary of measure zero.</li>
<li>The <strong>InShape</strong> implementation can determine only <em>pointwise</em> whether a point is either outside the shape, or on or inside the shape.</li>
<li>The <strong>InShape</strong> implementation has access to arbitrary-precision arithmetic, as well as interval arithmetic using arbitrary-precision rational numbers. See <a href="https://github.com/peteroupc/peteroupc.github.io/blob/master/interval.py"><strong>my library</strong></a>, for example.</li>
<li>Other than this, it doesn’t matter how the shape is described – it could be described as a sequence of line segments, curve segments, or both describing the shape’s outline; as a signed distance function; as an inequality; as a union or intersection of multiple shapes; etc.</li>
</ul>
<p>The <strong>InShape</strong> implementation is given an axis-aligned bounding box as input. The goal is to correctly classify the box just by evaluating the shape <em>pointwise</em>.</p>
<p>Under certain conditions, this is trivial to do. For example, if the shape is enclosed by a 1 × 1 rectangle, the point (0, 0) is on the shape, and every horizontal or vertical line crosses the shape (inside the rectangle) at most once (think of one quarter of a circle centered at the origin), then the box can be correctly classified just by checking the point’s corners. The algorithm (Algorithm 1) is thus to return—</p>
<ul>
<li><em>YES</em> if all the box’s vertices are on or inside the shape;</li>
<li><em>NO</em> if none of the box’s vertices are on or inside the shape; and</li>
<li><em>MAYBE</em> in any other case.</li>
</ul>
<p>More generally, I believe Algorithm 1 will work if—</p>
<ul>
<li>the shape is enclosed by a hypercube $[0, 1]\times[0, 1]\times…\times[0, 1]$,</li>
<li>the point $(0, 0, …, 0)$ is on or inside the shape, and</li>
<li>every open axis-aligned line segment that begins in one face of the hypercube and ends in another face crosses the shape at most once (an example is one quarter of a circular disk whose center is at $(0, 0)$),</li>
</ul>
<p>Or if—</p>
<ul>
<li>the shape is enclosed by a $2$-dimensional rectangle $[0, 1]\times[0, 1]$,</li>
<li>the line segment $((0, 0), (1, 1))$ is entirely on or inside the shape,</li>
<li>the shape is convex and symmetric about that line segment, and</li>
<li>the box being tested arose out of a recursive subdivision of the 2-dimensional rectangle into smaller boxes with half the size, $\frac{1}{4}$ the size, etc.</li>
</ul>
<p>However, for more general convex shapes (which are the shapes that I care about most), this is not so easy. For example, if the shape is convex and the point $(0, 0)$ is on the shape, the correct algorithm to classify the shape (Algorithm 2) is to return—</p>
<ul>
<li><em>YES</em> if all the box’s vertices are on or inside the shape;</li>
<li><em>NO</em> if none of the box’s vertices are on or inside the shape <em>and if the shape’s boundary does not intersect the box’s boundary</em>; and</li>
<li><em>MAYBE</em> in any other case.</li>
</ul>
<p>This is not so easy because checking whether a box intersects a shape might not be robust especially if the shape is described by an inequality (such as $x^2 + y^2 - 1 <= 0$). Under certain cases, the algorithm might miss an intersection even though it’s present. But at least when the shape is convex and when <strong>InShape</strong> uses interval arithmetic and builds one interval for each dimension of the box (here, $[x, x+\epsilon]$ and $[y, y+\epsilon]$), and evaluates the inequality only once with the intervals, <strong>InShape</strong> can still get robust results. In this algorithm (Algorithm 3), <strong>InShape</strong> returns—</p>
<ul>
<li><em>YES</em> if the result’s upper bound is less than 0;</li>
<li><em>NO</em> if the result’s lower bound is greater than 0; and</li>
<li><em>MAYBE</em> in any other case.</li>
</ul>
<p><a id="Questions_2"></a></p>
<h3 id="questions-1">Questions</h3>
<p>Thus my questions are:</p>
<ol>
<li>What are necessary or sufficient conditions (such as convexity or regularity conditions, or other requirements on the shape) that allow Algorithm 1 to work correctly? Are the sufficient conditions I gave above for this algorithm correct? If so, can they be relaxed?</li>
<li>What are necessary or sufficient conditions that allow Algorithm 2 to work correctly, if the <strong>InShape</strong> method can only evaluate the shape point-by-point? In particular, how can Algorithm 2 robustly check for intersections as required to determine whether to return <em>NO</em> or <em>MAYBE</em>?</li>
<li>What are other conditions that allow <strong>InShape</strong> to correctly classify whether a box is outside or on or inside a shape when <strong>InShape</strong> can only evaluate the shape point-by-point, or when <strong>InShape</strong> proceeds as in Algorithm 3?</li>
<li>
<p>Is it possible (or what additional conditions make it possible) to correctly classify a bounding box as <em>NO</em> or <em>MAYBE</em>, using only <em>pointwise</em> evaluation of the shape, if—</p>
<ul>
<li>the shape is enclosed by a hypercube $[0, 1]\times[0, 1]\times…\times[0, 1]$,</li>
<li>the point $(0, 0, …, 0)$ is on or inside the shape,</li>
<li>the shape is convex, and</li>
<li>the box being tested arose out of a recursive subdivision of the hypercube into smaller boxes with half the size, $\frac{1}{4}$ the size, etc.?</li>
</ul>
<p>(Note that in this case, classifying a bounding box as <em>YES</em> is trivial; just check its four corners. On the other hand, I know that it’s not enough to classify the box as <em>NO</em> or <em>MAYBE</em> this way.)</p>
</li>
</ol>
<p><a id="Examples"></a></p>
<h3 id="examples">Examples</h3>
<p>Take the following shapes, all of which are convex and equal 0 at the origin:</p>
<ul>
<li>$v^2 - (u/v)^{1.4-1}*exp(-(u/v)) \le 0$ - Ratio-of-uniforms shape for the gamma(1.4) distribution</li>
<li>$v^2 - exp(-(u/v)^2/2) \le 0$ - Ratio-of-uniforms shape for the normal distribution</li>
<li>$v^2 - (u/v)^2*exp(-(u/v)^2/2) \le 0$ - Ratio-of-uniforms shape for the Maxwell distribution</li>
</ul>
<p>All three shapes don’t work under Algorithm 1, but they appear to give correct results under Algorithm 3, even without the intersection checks required by Algorithm 2.</p>
<p><a id="Probabilities_arising_from_permutations"></a></p>
<h2 id="probabilities-arising-from-permutations">Probabilities arising from permutations</h2>
<p><a href="https://stats.stackexchange.com/questions/499864/probabilities-arising-from-permutations"><strong>https://stats.stackexchange.com/questions/499864/probabilities-arising-from-permutations</strong></a></p>
<p>Certain interesting probability functions can arise from permutations. For example, permutations that are sorted or permutations that form a cycle.</p>
<p>Inspired by the so-called <em>von Neumann schema</em> given in a paper called “<a href="https://arxiv.org/abs/0906.5560"><strong>On Buffon machines and numbers</strong></a>” by Flajolet and colleagues (2010), we can describe the following algorithm. To describe it, the following definition is needed:</p>
<ul>
<li>A <em>permutation class</em> is a rule that describes how a sequence of numbers must be ordered. The ordering of the numbers is called a <em>permutation</em>. Two examples of permutation classes cover permutations sorted in descending order, and permutations whose highest number appears first. When checking whether a sequence follows a permutation class, only less-than and greater-than comparisons between two numbers are allowed.</li>
</ul>
<p>The algorithm produces a discrete random variate based on a permutation class. Let $D$ and $E$ be absolutely continuous distributions.</p>
<ol>
<li>Create an empty list.</li>
<li>If the list is empty, generate a random variate distributed as $D$. Otherwise, generate a random variate distributed as $E$. Either way, append the random variate to the end of the list.</li>
<li>Let $n$ be the number of items in the list minus 1. If the items in the list do not form a permutation that meets the permutation class’s requirements, return $n$. Otherwise, go to step 2.</li>
</ol>
<p>If $D$ and $E$ are both uniform(0, 1), this algorithm returns the number <em>n</em> with the following probability:</p>
<p>\(G(n)= (1-\frac{V(n+1)}{V(n) (n+1)}) (1-\sum_{j=0}^{n-1} G(j))\)
\(= \frac{V(n) (n+1)-V(n+1)}{V(0) (n+1)!},\)</p>
<p>where $V(n) \in (0, n!]$ is the number of permutations of size <em>n</em> that meet the permutation class’s requirements. $V(n)$ can be a sequence associated with an <em>exponential generating function</em> (EGF) for the kind of permutation involved in the algorithm. (Examples of permutation classes include permutations whose numbers are sorted in descending order, or permutations whose first number is highest.) For example, if we use the class of permutations sorted in descending order, the EGF is $\exp(\lambda)$, so that $V(n)$ = 1.</p>
<p>For this algorithm, if $D$ and $E$ are both uniform(0, 1), the probability that the generated <em>n</em>—</p>
<ul>
<li>Is odd is $1-1/EGF(1)$, or</li>
<li>is even is $1 / EGF(1)$, or</li>
<li>is less than $k$ is $\frac{V(0)-V(k)/k!}{V(0)}$.</li>
</ul>
<p>Thus, for example, if we allow sorted permutations, the algorithm returns an odd number with probability that is <em>exactly</em> $1-\exp(-1)$.</p>
<p>Depending on the permutation class, the distributions $D$ and $E$, and which values of $n$ we care about, different probabilities and different distributions of numbers will arise. For example:</p>
<ul>
<li>If the class is sorted permutations, both $D$ and $E$ are the uniform distribution, and given that the return value $n$ is odd, it is known since von Neumann’s 1951 algorithm that that number has an exponential distribution limited to the interval [0, 1].</li>
<li>If the class is sorted permutations, both $D$ and $E$ are arbitrary distributions, and given that the return value $n$ is odd, then Forsythe (1972) and Monahan (1979) have characterized the distribution function of the sequence’s first number.</li>
</ul>
<p>See the tables in my section “<a href="https://peteroupc.github.io/bernoulli.html#Probabilities_Arising_from_Certain_Permutations"><strong>Probabilities Arising from Certain Permutations</strong></a>” for further examples.</p>
<p><a id="Questions_3"></a></p>
<h3 id="questions-2">Questions</h3>
<p>For a given permutation class, a given distribution $D$, and a given distribution $E$—</p>
<ul>
<li>what is the probability that the algorithm will return a particular $n$?</li>
<li>what is the probability that the algorithm will return an $n$ that belongs to a particular class of values (such as odd numbers or even numbers)?</li>
<li>what is the probability that the first number in the sequence is less than $x$ given that the algorithm returns $n$ (or one of a particular class of values of $n$)?</li>
<li>what is the probability that the last number in the sequence is less than $x$ given that the algorithm returns $n$ (or one of a particular class of values of $n$)?</li>
</ul>
<p>Note that the third part of the question is equivalent to: What is the CDF of the first number’s distribution given that $n$ is returned? Similarly for the fourth part of the question.</p>
<p><a id="Questions_on_Estimation_Algorithms"></a></p>
<h2 id="questions-on-estimation-algorithms">Questions on Estimation Algorithms</h2>
<p><a href="https://stats.stackexchange.com/questions/522429/estimating-f-mathbbex-with-a-guaranteed-error-performance"><strong>https://stats.stackexchange.com/questions/522429/estimating-f-mathbbex-with-a-guaranteed-error-performance</strong></a></p>
<p><a href="https://stats.stackexchange.com/questions/555066/a-generalized-randomized-mean-estimate-based-on-the-chebyshev-inequality"><strong>https://stats.stackexchange.com/questions/555066/a-generalized-randomized-mean-estimate-based-on-the-chebyshev-inequality</strong></a></p>
<p>Let $X$ be a random variable that does not take on a single value with probability 1. Let “black-box” i.i.d. sample access to the random variable $X$ be given. Let $f(x)$ be a known function belonging to a given class of functions.</p>
<ol>
<li>
<p>Suppose $f(x)$ is continuous, and suppose $X$ is unbounded and meets additional assumptions, such as—</p>
<ul>
<li>being unimodal (having one peak) and symmetric (mirrored on each side of the peak), or</li>
<li>following a geometric distribution, or</li>
<li>having decreasing or nowhere increasing probabilities,</li>
</ul>
<p>or any combination of these. Then, is there an algorithm, besides the algorithm of Kunsch et al. (2019)—</p>
<ul>
<li>whose output is within $\epsilon$ of $f(\mathbb{E}[X])$ in terms of absolute error with probability at least 1 minus $\delta$, or</li>
<li>whose output has an expected absolute error or mean squared error not more than $\epsilon$,</li>
</ul>
<p>where $\epsilon$ and $\delta$ are user-specified values? (Relative error means $\text{abs}(\hat\mu/f(\mathbb{E}[X])-1)$ where $\hat\mu$ is the estimate.)</p>
<p>Notice that merely having finite moments is not enough (Theorem 3.4, Kunsch et al.). My article on <a href="https://peteroupc.github.io/estimation.html"><strong>estimation algorithms</strong></a> already gives a relative-error algorithm for the geometric distribution in a note.</p>
</li>
<li>
<p>Let $M_k$ be an upper bound on the $k$th central absolute moment of $X$, for $k>1$. <a href="https://stats.stackexchange.com/questions/555066/a-generalized-randomized-mean-estimate-based-on-the-chebyshev-inequality"><strong>Based on the Chebyshev inequality</strong></a> (as well as Hickernell et al. 2013; Kunsch et al. 2018), is the mean $\mathbb{E}[X]$ within $\epsilon$ of the mean of $n$ i.i.d. samples, where— \(n=\left\lceil\frac{M_k}{\delta\epsilon^k}\right\rceil,\) with probability at least $1-\delta$?</p>
<p>If so: Let $f(x)$ be uniformly continuous on the real line. Let $m(\epsilon)$ be an inverse modulus of continuity of $f$, that is, a function that satisfies $\text{abs}(f(y)-f(z))<\epsilon$ whenever $\text{abs}(y-z)<m(\epsilon)$. Then is $f(\mathbb{E}[X])$ within $\epsilon$ of the mean of $f$ on $n$ i.i.d. samples, where— \(n=\left\lceil\frac{M_k}{\delta(m(\epsilon))^k}\right\rceil,\) with probability at least $1-\delta$? In both questions, $\epsilon$ and $\delta$ are user-specified values.</p>
</li>
<li>
<p>Let $g$ be a known piecewise continuous function on [0, 1], and suppose $X$ lies on the interval [0, 1]. How can <a href="https://stats.stackexchange.com/a/523355/296678"><strong>a Stack Exchange answer</strong></a> be adapted to $g$, so that the algorithm estimates $g(\mathbb{E}[X])$ with either a high probability of a “small” absolute error or one of a “small” relative error at all points in [0, 1] except at a “negligible” area around $g$’s discontinuities? Is it enough to replace $g$ with a continuous function $f$ that equals $g$ everywhere except at that “negligible” area? Here, the accuracy tolerances for small error, high probability, and “negligible” area are user-specified. Perhaps the tolerance could be defined as the integral of absolute differences between $f$ and $g$ instead of “negligible area”; in that case, how should the continuous $f$ be built?</p>
</li>
<li>
<p>If $X$ is Bernoulli with unknown mean 0 < <em>λ</em> ≤ 1, is the following algorithm an unbiased estimator of 1/<em>λ</em>? Take random variates i.i.d. until a 1 is taken, then count the number of variates taken this way. This question is asked because the results of Jacob and Thiery (2015) don’t cover the case of whether a nonnegative unbiased estimator of $f(\mathbb{E}[X])$ exists when $f:(a,b]\to[0,\infty)$ is unbounded, as opposed to when $f$ is bounded or when $f$’s <em>domain</em> is unbounded or a <em>closed</em> interval.</p>
</li>
</ol>
<p><a id="References"></a></p>
<h2 id="references">References</h2>
<ul>
<li>Hickernell, F.J., Jiang, L., et al., “<a href="https://arxiv.org/abs/1208.4318v3"><strong>Guaranteed Conservative Fixed Width Intervals via Monte Carlo Sampling</strong></a>”, arXiv:1208.4318v3 [math.ST], 2012/2013.</li>
<li>Kunsch, Robert J., Erich Novak, and Daniel Rudolf. “Solvable integration problems and optimal sample size selection.” Journal of Complexity 53 (2019): 40-67.</li>
<li>Forsythe, G.E., “Von Neumann’s Comparison Method for Random Sampling from the Normal and Other Distributions”, <em>Mathematics of Computation</em> 26(120), October 1972.</li>
<li>Monahan, J. “Extensions of von Neumann’s method for generating random variables.” Mathematics of Computation 33 (1979): 1065-1069.</li>
<li>Knuth, Donald E. And Andrew Chi-Chih Yao. “The complexity of nonuniform random number generation”, in Algorithms and Complexity: New Directions and Recent Results, 1976.</li>
<li>Vatan, F., “Distribution functions of probabilistic automata”, in Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC ‘01), pp. 684-693, 2001.</li>
<li>Kindler, Guy and D. Romik, “On distributions computable by random walks on graphs, “ SIAM Journal on Discrete Mathematics 17 (2004): 624-633.</li>
<li>Adamczewski, B., Cassaigne, J. And Le Gonidec, M., 2020. On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited. Transactions of the American Mathematical Society, 373(5), pp.3085-3115.</li>
<li>Yao, Andrew C. “Context-free grammars and random number generation.” In Combinatorial algorithms on words, pp. 357-361. Springer, Berlin, Heidelberg, 1985.</li>
<li>Jacob, P.E., Thiery, A.H., “On nonnegative unbiased estimators”, Ann. Statist., Volume 43, Number 2 (2015), 769-784.</li>
</ul>
<p><a id="License"></a></p>
<h2 id="license">License</h2>
<p>Any copyright to this page is released to the Public Domain. In case this is not possible, this page is also licensed under <a href="https://creativecommons.org/publicdomain/zero/1.0/"><strong>Creative Commons Zero</strong></a>.</p>
</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/requestsother.pdf'>Download a PDF of this page</a></p></nav></body></html>