You are currently browsing the monthly archive for May 2011.

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.

Let’s jump straight in. Suppose I have a collection of *n* different objects, where *n* is some unknown but fixed whole number. Suppose I want to arrange *k* of them in a row on my shelf, where *k* is some unknown but fixed whole number less than or equal to *n*. In how many ways can this be done?

This is a counting problem. You are being asked to count how many of something there are. The answer will be a formula involving the unknown quantities *n* and *k*. Counting is often thought of as being easy. While it is true that the things which must be counted are easy to describe (I have just done so in a couple of sentences), this does not mean that the problem of counting them is easy. So, in this post I continue my quest to explain some basic things about counting and how to do it.

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.