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.