In this post we will look at random partitions. A partition of is a set of disjoint subsets of such that . We arrange these sets in the order of their least element, so that , and if there are only finitely many subsets, we trail the sequence with emptysets, e.g. . Denote the set of partitions of by .
Notice that each induces an equivalence relation on by if and only if and belong to the same block of . Now let be a permutation of , and we define a partition by saying that and are in the same block of if and only if .
Suppose now that is a random partition. We say that is exchangeable if for each permutation which changes finitely many elements, we have that has the same distribution as .
There is a wonderful theorem by Kingman which will follow shortly but for now let us look at some basic properties of random exchangeable partitions.
Firstly I will show that if there are any singletons, then there are infinitely many of them a.s. Suppose that for some , we have that under this is a singleton with probability . Now pick any , and consider the permutation which swaps and and fixes everything else. By the virtue of exchangeability we see that as has the same law as , now has probability of being a singleton. Thus every natural number has probability of being a singleton, which by the Borel-Cantelli lemma we have that there are infinity many singletons. The singletons of a partition are referred to as dust.
Another interesting area is to look at the asymptotic frequency of a block of which is defined by
where is the number of elements of a set . We will soon see that these quantities exist but for now if they exist let us denote the decreasing sequence of them by so that is the largest asymptotic frequency that any blocks of posses.
It also turns out there is an elegant way to construct an exchangeable random partition using the paintbox method. Let which are called the mass partitions. The parameter will play the role of dust, so it is useful to allow for strict inequality when defining mass partitions.
Now pick an and slice up the interval into segments of length and so forth, i.e. we have intervals and if , label the remaining interval dust (if , then this partitioning mechanism doesn’t cover the whole of ). Suppose now we start dropping i.i.d. uniform random variables on to , we say that
if and only if and fall in to the same segment constructed above which is not the dust segment.
So why is this partition exchangeable? Well if is a permutation which fixes all but finitely many points, then as the sequence is i.i.d., the probability that and fall in the same block for is the same as any other pair. We denote by the law of the exchangeable random partition obtained by . First let us prove an easy lemma about the asymptotic frequencies of paintbox partitions.
Let and denote by the random partition with law , obtained by the paintbox construction above. Then the asymptotic frequencies of exist a.s. and moreover .
Consider a set for some , and let be sequence of i.i.d. uniform random variables. Then the sequence of random variables are i.i.d. with mean . Thus the block which is generated by this interval has asymptotic frequency given by
by the strong law of large numbers.
A natural question to ask would be that if we are given a random , can we find an such that is distributed ? It turns out that it is not that simple, however Kingman proved the following result.
Theorem: (Kingman’s Correspondence)
Let be an exchangeable random partition, then possesses asymptotic frequencies and moreover
This theorem tells us that an exchangeable random partition is a mixture of paintboxes. The original proof of it by Kingman relied on a martingale argument but we shall present a proof first given by Aldous. This proof relies on de Finetti’s theorem on exchangeable random variables.
Theorem: (de Finetti)
Let be a sequence of exchangeable random variables, i.e. for every permutation , the joint distribution of is the same as . Then there exists a random probability measure , such that conditionally on , the random variables are i.i.d. with law .
This notion of exchangeable random variables was introduced to weaken the assumptions of being i.i.d. One can immediately see that if are i.i.d. then they are exchangeable and the theorem is trivial (the random measure is not random). The proof for the general case can be found in most textbooks and we shall skip it here. The proof for Kingman’s correspondence I give here is from Bertoin (see further reading below).
Proof of Kingman’s Correspondence:
For any partition we say that is a selection map if it maps each element of a block of to the same point in that block. For example is the infimum of the block containing . Let be a sequence of i.i.d. uniform random variables, independent of everything else and define . Then we claim that is an exchangeable sequence of random variables. So let be a permutation and .
On the one hand is a selection map for and on the other we have that where . The random variables are i.i.d. uniforms, independent of and and so have the joint laws of and are the same. Thus the sequence is exchangeable.
By de Finetti’s theorem there exists a random measure on such that conditionally on , are i.i.d. with law . Define
Let be an i.i.d. sequence of uniform random variables on , which is independent of everything else. Then conditionally on , the law of corresponds with the law of . Now if and only if , which has the same probability as . This only happens when and fall in to the same flat component of . More precisely let partition in to intervals where for each we have and label the remaining intervals dust. Notice now that conditionally on
if and only if and fall in to the same interval which is not the dust interval
which is a paintbox construction.
- Jean Bertoin, Random Fragmentation and Coagulation Processes
- Nathanael Berestycki, Recent Progress in Coalescent Theory