The Poisson-Dirichlet process, and large prime factors of a random number

Define a partition of to be a finite or infinite multiset of real numbers in the interval (that is, an unordered set of real numbers in , possibly with multiplicity) whose total sum is : . For instance, is a partition of . Such partitions arise naturally when trying to decompose a large object into smaller ones, for instance:

1. (Prime factorisation) Given a natural number , one can decompose it into prime factors (counting multiplicity), and then the multiset

   

   is a partition of .

2. (Cycle decomposition) Given a permutation on labels , one can decompose into cycles , and then the multiset

   

   is a partition of .

3. (Normalisation) Given a multiset of positive real numbers whose sum is finite and non-zero, the multiset

   

   is a partition of .

In the spirit of the universality phenomenon, one can ask what is the natural distribution for what a “typical” partition should look like; thus one seeks a natural probability distribution on the space of all partitions, analogous to (say) the gaussian distributions on the real line, or GUE distributions on point processes on the line, and so forth. It turns out that there is one natural such distribution which is related to all three examples above, known as the Poisson-Dirichlet distribution. To describe this distribution, we first have to deal with the problem that it is not immediately obvious how to cleanly parameterise the space of partitions, given that the cardinality of the partition can be finite or infinite, that multiplicity is allowed, and that we would like to identify two partitions that are permutations of each other

One way to proceed is to random partition as a type of point process on the interval , with the constraint that , in which case one can study statistics such as the counting functions

(where the cardinality here counts multiplicity). This can certainly be done, although in the case of the Poisson-Dirichlet process, the formulae for the joint distribution of such counting functions is moderately complicated. Another way to proceed is to order the elements of in decreasing order

with the convention that one pads the sequence by an infinite number of zeroes if is finite; this identifies the space of partitions with an infinite dimensional simplex

However, it turns out that the process of ordering the elements is not “smooth” (basically because functions such as and are not smooth) and the formulae for the joint distribution in the case of the Poisson-Dirichlet process is again complicated.

It turns out that there is a better (or at least “smoother”) way to enumerate the elements of a partition than the ordered method, although it is random rather than deterministic. This procedure (which I learned from this paper of Donnelly and Grimmett) works as follows.

1. Given a partition , let be an element of chosen at random, with each element having a probability of being chosen as (so if occurs with multiplicity , the net probability that is chosen as is actually ). Note that this is well-defined since the elements of sum to .
2. Now suppose is chosen. If is empty, we set all equal to zero and stop. Otherwise, let be an element of chosen at random, with each element having a probability of being chosen as . (For instance, if occurred with some multiplicity in , then can equal with probability .)
3. Now suppose are both chosen. If is empty, we set all equal to zero and stop. Otherwise, let be an element of , with ech element having a probability of being chosen as .
4. We continue this process indefinitely to create elements .

We denote the random sequence formed from a partition in the above manner as the random normalised enumeration of ; this is a random variable in the infinite unit cube , and can be defined recursively by the formula

with drawn randomly from , with each element chosen with probability , except when in which case we instead have

Note that one can recover from any of its random normalised enumerations by the formula

with the convention that one discards any zero elements on the right-hand side. Thus can be viewed as a (stochastic) parameterisation of the space of partitions by the unit cube , which is a simpler domain to work with than the infinite-dimensional simplex mentioned earlier.

Note that this random enumeration procedure can also be adapted to the three models described earlier:

1. Given a natural number , one can randomly enumerate its prime factors by letting each prime factor of be equal to with probability , then once is chosen, let each remaining prime factor of be equal to with probability , and so forth.
2. Given a permutation , one can randomly enumerate its cycles by letting each cycle in be equal to with probability , and once is chosen, let each remaining cycle be equalto with probability , and so forth. Alternatively, one traverse the elements of in random order, then let be the first cycle one encounters when performing this traversal, let be the next cycle (not equal to one encounters when performing this traversal, and so forth.
3. Given a multiset of positive real numbers whose sum is finite, we can randomly enumerate the elements of this sequence by letting each have a probability of being set equal to , and then once is chosen, let each remaining have a probability of being set equal to , and so forth.

We then have the following result:

Proposition 1 (Existence of the Poisson-Dirichlet process) There exists a random partition whose random enumeration has the uniform distribution on , thus are independently and identically distributed copies of the uniform distribution on .

A random partition with this property will be called the Poisson-Dirichlet process. This process, first introduced by Kingman, can be described explicitly using (1) as

where are iid copies of the uniform distribution of , although it is not immediately obvious from this definition that is indeed uniformly distributed on . We prove this proposition below the fold.

An equivalent definition of a Poisson-Dirichlet process is a random partition with the property that

where is a random element of with each having a probability of being equal to , is a uniform variable on that is independent of , and denotes equality of distribution. This can be viewed as a sort of stochastic self-similarity property of : if one randomly removes one element from and rescales, one gets a new copy of .

It turns out that each of the three ways to generate partitions listed above can lead to the Poisson-Dirichlet process, either directly or in a suitable limit. We begin with the third way, namely by normalising a Poisson process to have sum :

Proposition 2 (Poisson-Dirichlet processes via Poisson processes) Let , and let be a Poisson process on with intensity function . Then the sum is almost surely finite, and the normalisation is a Poisson-Dirichlet process.

Again, we prove this proposition below the fold. Now we turn to the second way (a topic, incidentally, that was briefly touched upon in this previous blog post):

Proposition 3 (Large cycles of a typical permutation) For each natural number , let be a permutation drawn uniformly at random from . Then the random partition converges in the limit to a Poisson-Dirichlet process in the following sense: given any fixed sequence of intervals (independent of ), the joint discrete random variable converges in distribution to .

Finally, we turn to the first way:

Proposition 4 (Large prime factors of a typical number) Let , and let be a random natural number chosen according to one of the following three rules:

1. (Uniform distribution) is drawn uniformly at random from the natural numbers in .
2. (Shifted uniform distribution) is drawn uniformly at random from the natural numbers in .
3. (Zeta distribution) Each natural number has a probability of being equal to , where and .

Then converges as to a Poisson-Dirichlet process in the same fashion as in Proposition 3.

The process was first studied by Billingsley (and also later by Knuth-Trabb Pardo and by Vershik, but the formulae were initially rather complicated; the proposition above is due to of Donnelly and Grimmett, although the third case of the proposition is substantially easier and appears in the earlier work of Lloyd. We prove the proposition below the fold.

The previous two propositions suggests an interesting analogy between large random integers and large random permutations; see this ICM article of Vershik and this non-technical article of Granville (which, incidentally, was once adapted into a play) for further discussion.

As a sample application, consider the problem of estimating the number of integers up to which are not divisible by any prime larger than (i.e. they are -smooth), where is a fixed real number. This is essentially (modulo some inessential technicalities concerning the distinction between the intervals and ) the probability that avoids , which by the above theorem converges to the probability that avoids . Below the fold we will show that this function is given by the Dickman function, defined by setting for and for , thus recovering the classical result of Dickman that .

I thank Andrew Granville and Anatoly Vershik for showing me the nice link between prime factors and the Poisson-Dirichlet process. The material here is standard, and (like many of the other notes on this blog) was primarily written for my own benefit, but it may be of interest to some readers. In preparing this article I found this exposition by Kingman to be helpful.

Note: this article will emphasise the computations rather than rigour, and in particular will rely on informal use of infinitesimals to avoid dealing with stochastic calculus or other technicalities. We adopt the convention that we will neglect higher order terms in infinitesimal calculations, e.g. if is infinitesimal then we will abbreviate simply as .

The number of cycles in a random permutation

Let be a natural number, and let be a permutation of , drawn uniformly at random. Using the cycle decomposition, one can view as the disjoint union of cycles of varying lengths (from to ). For each , let denote the number of cycles of of length ; thus the are natural number-valued random variables with the constraint

We let be the number of cycles (of arbitrary length); this is another natural number-valued random variable, of size at most .

I recently had need to understand the distribution of the random variables and . As it turns out this is an extremely classical subject, but as an exercise I worked out what I needed using a quite tedious computation involving generating functions that I will not reproduce here. But the resulting identities I got were so nice, that they strongly suggested the existence of elementary bijective (or “double counting”) proofs, in which the identities are proven with a minimum of computation, by interpreting each side of the identity as the cardinality (or probability) of the same quantity (or event), viewed in two different ways. I then found these bijective proofs, which I found to be rather cute; again, these are all extremely classical (closely related, for instance, to Stirling numbers of the first kind), but I thought some readers might be interested in trying to find these proofs themselves as an exercise (and I also wanted a place to write the identities down so I could retrieve them later), so I have listed the identities I found below.

1. For any , one has . In particular, .
2. More generally, for any and with , one has .
3. More generally still, for any and with , one has

   

4. In particular, we have Cauchy’s formula: if , then the probability that for all is precisely . (This in particular leads to a reasonably tractable formula for the joint generating function of the , which is what I initially used to compute everything that I needed, before finding the slicker bijective proofs.)
5. For fixed , converges in distribution as to the Poisson distribution of intensity .
6. More generally, for fixed , converge in joint distribution to independent Poisson distributions of intensity respectively. (A more precise version of this claim can be found in this paper of Arratia and Tavaré.)
7. One has .
8. More generally, one has for all natural numbers .