7
$\begingroup$

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:

  • A permutation class is a rule that describes how a sequence of numbers must be ordered. The ordering of the numbers is called a permutation. 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.

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:

$$\eqalign{ 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

  • Is odd is $1-1/EGF(1)$, or
  • is even is $1 / EGF(1)$, or
  • is less than $k$ is $\frac{V(0)-V(k)/k!}{V(0)}$.

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:

  • 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 a truncated exponential distribution.
  • 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.

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

For these reasons, it seems to me that this algorithm can open the door to new and exact samplers for continuous and discrete distributions, including new and exact ways to sample certain irrational probabilities. (And I list many of them in "Bernoulli Factory Algorithms".) And this is why I ask the following questions:

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

  • what is the probability that the algorithm will return a particular $n$?
  • 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)?
  • 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$)?
  • 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$)?

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.

REFERENCES:

  • Forsythe, G.E., "Von Neumann's Comparison Method for Random Sampling from the Normal and Other Distributions", Mathematics of Computation 26(120), October 1972.
  • Monahan, J. "Extensions of von Neumann’s method for generating random variables." Mathematics of Computation 33 (1979): 1065-1069.
$\endgroup$
6
  • 3
    $\begingroup$ I stopped reading near the beginning because I don't know what you might mean by a list of real numbers being a "valid permutation" and this is crucial to understanding all that follows. According to the standard mathematical definition (a permutation is a bijection of a set to itself), the ranks of any finite or countable set of iid uniform numbers drawn from a nontrivial interval will almost surely be a permutation, leading me to conclude your algorithm will almost surely never terminate. Could you explain? $\endgroup$
    – whuber
    Dec 8, 2020 at 16:42
  • 1
    $\begingroup$ @whuber: In my question, a "valid permutation" means a permutation that meets the requirements of the permutation class in question. For instance, for the class of sorted permutations, a permutation is valid if the numbers in it are listed in ascending order; for the class of all permutations, all permutations are valid; and for the class of cyclic permutations, a permutation is valid if the first number in it is the highest. $\endgroup$
    – Peter O.
    Dec 8, 2020 at 16:49
  • $\begingroup$ @whuber: Of course, this algorithm will not work for all permutation classes. $\endgroup$
    – Peter O.
    Dec 8, 2020 at 16:55
  • $\begingroup$ Interesting -- thank you for the explanation. $\endgroup$
    – whuber
    Dec 8, 2020 at 17:01
  • 1
    $\begingroup$ I'm not sure if I'm missing something but aren't the answers to all of your questions incredibly dependent on the specific permutation classes and distributions defined? As in the example you gave the answers you gave are only that nice because sorted permutations give nice restrictions, and letting $D = E$ also makes things much simpler. Granted I don't know much about defining RV's algorithmically this way and I could very much be missing something, but it seemed very cool and was an interesting problem to think about for a bit but also incredibly wide of a problem $\endgroup$
    – Dale C
    Jan 4, 2021 at 14:00

1 Answer 1

0
$\begingroup$

For arbitrary distributions $D$ and $E$ and for the permutation class of descending numbers, the algorithm I presented returns $n$ with the probability—

  • $\int_{-\infty}^{\infty} (\frac{F_E(z)^{n-1}}{(n-1)!} - \frac{F_E(z)^n}{n!}) dF_D(z)$ if $n \ge 1$, and
  • 0 otherwise,

Where $F_D$ and $F_E$ are distribution functions of $D$ and $E$ (note that if $D$ has a density function $f_D$, then $dF_D(z) = f_D(z) dz$).

For this result, I was inspired by Theorem 2.1 given in chapter 4 of Non-Uniform Random Variate Generation. See also Forsythe 1972.

That leaves the question of what probabilities arise with arbitrary distributions (not just uniform) under arbitrary permutation classes (not just numbers in descending order).


EDIT (Nov. 5): Whenever $D = E$ (not just if $D$ is uniform), then $n$ is odd with probability $1-\exp(-1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.