Requests and Open Questions

Peter Occil

This page lists questions and issues relating to my articles posted on this site. Any answers to these questions will greatly improve those articles. If you can answer any of them, post an issue in the GitHub issues page.

Contents

My Probability Questions

The following two pages describe questions I have also posted on MathOverflow and other Stack Exchange sites. Can you help answer any of these? Answers to them will greatly improve my articles on this site.

Randomization and Sampling Methods

Size Reduction Sought:

Of the articles in this repository, Randomization and Sampling Methods and More Random Sampling Methods combined are very long.

These articles describe numerous algorithms to generate random variates (from discrete and continuous distributions) as well as perform random sampling with and without replacement, shuffling, geometric sampling, and more, assuming a source of "truly" random numbers is available.

I would like to reduce the size of these articles while maintaining the most relevant algorithms for random variate generation.

Here are my goals for both articles:

Bernoulli Factory Algorithms

This page shows algorithms to turn a coin with an unknown probability of heads into a coin with a different probability of heads, also known as Bernoulli factories. A factory function is a function that relates the old probability to the new one. Roughly speaking, a function can be a factory function only if it is the constant 0 or 1, or if it is continuous on its domain and equals neither 0 nor 1 on the open interval (0, 1) (Keane and O'Brien 1994)[^1].

For open questions, see "Open Questions on the Bernoulli Factory Problem".

Partially-Sampled Random Numbers

This page describes a structure for storing a random variate with arbitrary precision.

  1. We would like to see new implementations of the following:
    • Algorithms that implement InShape for specific closed curves, specific closed surfaces, and specific signed distance functions. Recall that InShape determines whether a box lies inside, outside, or partly inside or outside a given curve or surface.
    • Descriptions of algorithms for non-discrete distributions that satisfy the properties for partially-sampled random number algorithms.
    • Descriptions of new arbitrary-precision algorithms that use the skeleton given in the section "Building an Arbitrary-Precision Sampler".
  2. Take a polynomial f(λ) of even degree n of the form choose(n,n/2)*λn/2*(1−λ)n/2*k, where k is greater than 1 (thus all f's Bernstein coefficients are 0 except for the middle one, which equals k). Suppose f(1/2) lies in the interval (0, 1). If we do the degree elevation enough times (at least r times), then f's Bernstein coefficients will all lie in [0, 1]. The question is: how many degree elevations are enough? A MathOverflow answer showed that r is at least m = (n/f(1/2)2)/(1−f(1/2)2), but is it true that floor(m)+1 elevations are enough?

For other open questions, see "Other Open Questions on Probability".

Randomized Estimation Algorithms

https://peteroupc.github.io/estimation.html

For open questions, see "Questions on Estimation Algorithms" and "The Sampling Problem".

Color Topics for Programmers

https://peteroupc.github.io/colorgen.html

Should this document cover the following topics, and if so, how?

Does any of the following exist?

Notes

[^1]: Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994.

License

Any copyright to this page is released to the Public Domain. In case this is not possible, this page is also licensed under Creative Commons Zero.