Other Open Questions on Probability

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 GitHub issues page.

Contents

Additional Requests and Open Questions

Besides the requests and open questions found here, the following pages list others:

Probability distributions computable by pushdown automata

https://cstheory.stackexchange.com/questions/50826/probability-distributions-generated-by-pushdown-automata

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 pushdown automata (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 pushdown generators, defined next.

Pushdown Generators

A pushdown generator has a finite set of states and a finite set of stack symbols, 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:

In the transition rules above, digit 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 0.dddddd..., where dddddd... are the digits produced by the machine from left to right.

See also Yao 1985.

A finite-state generator (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 finite automaton driven by fair coin flips.)

Distributions Computable by Pushdown Generators

The question that interests me is which probability distributions of real numbers can be computed by pushdown generators, and how they can be constructed.

For example, a pushdown generator with a loop that outputs 0 or 1 at an equal chance produces a uniform distribution.

In this sense, there are existing results for finite-state generators. For example:

Also, I believe that the following results are true:

  1. 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.
  2. 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.

Questions

The first question is whether the two results at the end of the previous section are true.

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):

  1. Of the probability distributions that a finite-state generator can generate, what is the exact class of:

    • Discrete distributions (those that cover a finite or countably infinite set of values)?
    • Absolutely continuous distributions (those with a probability density function such as the uniform or triangular distribution)?
    • Singular distributions (covering an uncountable but measure-zero set)?
    • Absolutely continuous distributions with continuous density functions?

  2. Same question as 1, but for pushdown generators.

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

Checking if a shape covers a box

https://math.stackexchange.com/questions/3882545/what-conditions-ensure-that-checking-if-a-shape-covers-a-box-can-be-done-just-by

I have described an algorithm for generating random points inside an arbitrary shape (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—

This algorithm uses a function called InShape that determines whether a shape covers an axis-aligned bounding box. It takes such a bounding box as input and returns—

Now, take a particular implementation of InShape that has certain knowledge about a particular shape. Assume the following:

The InShape implementation is given an axis-aligned bounding box as input. The goal is to correctly classify the box just by evaluating the shape pointwise.

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—

More generally, I believe Algorithm 1 will work if—

Or if—

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—

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 InShape 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, InShape can still get robust results. In this algorithm (Algorithm 3), InShape returns—

Questions

Thus my questions are:

  1. 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?
  2. What are necessary or sufficient conditions that allow Algorithm 2 to work correctly, if the InShape 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 NO or MAYBE?
  3. What are other conditions that allow InShape to correctly classify whether a box is outside or on or inside a shape when InShape can only evaluate the shape point-by-point, or when InShape proceeds as in Algorithm 3?

  4. Is it possible (or what additional conditions make it possible) to correctly classify a bounding box as NO or MAYBE, using only pointwise evaluation of the shape, if—

    • the shape is enclosed by a hypercube $[0, 1]\times[0, 1]\times…\times[0, 1]$,
    • the point $(0, 0, …, 0)$ is on or inside the shape,
    • the shape is convex, and
    • 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.?

    (Note that in this case, classifying a bounding box as YES is trivial; just check its four corners. On the other hand, I know that it’s not enough to classify the box as NO or MAYBE this way.)

Examples

Take the following shapes, all of which are convex and equal 0 at the origin:

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.

Probabilities arising from permutations

https://stats.stackexchange.com/questions/499864/probabilities-arising-from-permutations

Certain interesting probability functions can arise from permutations. For example, permutations that are sorted or permutations that form a cycle.

Inspired by the so-called von Neumann schema given in a paper called “On Buffon machines and numbers” by Flajolet and colleagues (2010), we can describe the following algorithm. To describe it, the following definition is needed:

The algorithm produces a discrete random variate based on a permutation class. Let $D$ and $E$ be absolutely continuous distributions.

  1. Create an empty list.
  2. 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.
  3. 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.

If $D$ and $E$ are both uniform(0, 1), this algorithm returns the number n with the following probability:

\(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)!},\)

where $V(n) \in (0, n!]$ is the number of permutations of size n that meet the permutation class’s requirements. $V(n)$ can be a sequence associated with an exponential generating function (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.

For this algorithm, if $D$ and $E$ are both uniform(0, 1), the probability that the generated n—

Thus, for example, if we allow sorted permutations, the algorithm returns an odd number with probability that is exactly $1-\exp(-1)$.

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:

See the tables in my section “Probabilities Arising from Certain Permutations” for further examples.

Questions

For a given permutation class, a given distribution $D$, and a given distribution $E$—

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.

Questions on Estimation Algorithms

https://stats.stackexchange.com/questions/522429/estimating-f-mathbbex-with-a-guaranteed-error-performance

https://stats.stackexchange.com/questions/555066/a-generalized-randomized-mean-estimate-based-on-the-chebyshev-inequality

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.

  1. Suppose $f(x)$ is continuous, and suppose $X$ is unbounded and meets additional assumptions, such as—

    • being unimodal (having one peak) and symmetric (mirrored on each side of the peak), or
    • following a geometric distribution, or
    • having decreasing or nowhere increasing probabilities,

    or any combination of these. Then, is there an algorithm, besides the algorithm of Kunsch et al. (2019)—

    • whose output is within $\epsilon$ of $f(\mathbb{E}[X])$ in terms of absolute error with probability at least 1 minus $\delta$, or
    • whose output has an expected absolute error or mean squared error not more than $\epsilon$,

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

    Notice that merely having finite moments is not enough (Theorem 3.4, Kunsch et al.). My article on estimation algorithms already gives a relative-error algorithm for the geometric distribution in a note.

  2. Let $M_k$ be an upper bound on the $k$th central absolute moment of $X$, for $k>1$. Based on the Chebyshev inequality (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$?

    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.

  3. Let $g$ be a known piecewise continuous function on [0, 1], and suppose $X$ lies on the interval [0, 1]. How can a Stack Exchange answer 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?

  4. If $X$ is Bernoulli with unknown mean 0 < λ ≤ 1, is the following algorithm an unbiased estimator of 1/λ? 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 domain is unbounded or a closed interval.

References

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.