You are currently browsing the tag archive for the ‘random partitions’ tag.

If you haven’t read my previous post, I would suggest doing so before this. We denote by the partitions of . The thing to keep in mind here is that we want to think of a coalescent process as a history of lineage. Suppose we start with the trivial partition and think of each block as a member of some population. A coalescent process on is essentially defines ancestries, in the sense that if and belong to the same block of for some , then we think of that block as the common ancestor of and .

With this in mind, define the operator by

.

With some conditions, we can define the same operator on , the partitions of . So for example if and , then . The partition tells us in this case to merge the first and third block and leave the second block alone.

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.