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

• Contents
• My Probability Questions
• Randomization and Sampling Methods
• Bernoulli Factory Algorithms
• Partially-Sampled Random Numbers
• Randomized Estimation Algorithms
• Color Topics for Programmers
• Notes
• License

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.

• Open Questions on the Bernoulli Factory Problem
• Other Open Questions on Probability

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:

• To shorten the Randomization with Real Numbers section as much as possible, while still describing the most general (and exact) algorithms possible for sampling real numbers of any distribution.
• To put emphasis on algorithms that work with random integers (or, if necessary, rational numbers), rather than random floating-point numbers.
• To put emphasis on algorithms that sample a distribution exactly, or at least with a controlled upper bound on the error. For discussion, see “Exact, Error-Bounded, and Approximate Algorithms”.
• To ensure the documents are easy for programmers to understand and implement.

Bernoulli Factory Algorithms

• https://peteroupc.github.io/bernoulli.html

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)¹.

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

Partially-Sampled Random Numbers

• https://peteroupc.github.io/exporand.html

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)²)/(1−f(1/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?

• The CAM02 color appearance model.
• Color rendering metrics for light sources, including color rendering index (CRI) and the metrics given in TM-30-15 by the Illuminating Engineering Society.

Does any of the following exist?

• A method for performing color calibration and color matching using a smartphone’s camera and, possibly, a color calibration card or white balance card, provided that method is not covered by any active patents or pending patent applications.
• Reference source code for a method to match a desired color on paper given spectral reflectance curves of the paper and of the inks being used in various concentrations, provided that method is not covered by any active patents or pending patent applications.

Notes

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.