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 $\mathcal{P}_\infty$ the partitions of $\mathbb{N}$. 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 $(\{1\},\{2\},\dots)$ and think of each block $\{i\}$ as a member of some population. A coalescent process $\Pi=(\Pi(t) :t \geq 0)$ on $\mathcal{P}_\infty$ is essentially defines ancestries, in the sense that if $i$ and $j$ belong to the same block of $\Pi(t)$ for some $t\geq 0$, then we think of that block as the common ancestor of $i$ and $j$.

With this in mind, define the operator $Coag:\mathcal{P}_\infty \times \mathcal{P}_\infty \rightarrow \mathcal{P}_\infty$ by

$Coag(\pi,\pi')_i=\bigcup_{j \in \pi'}\pi_j$.

With some conditions, we can define the same operator on $\mathcal{P}_{[n]}$, the partitions of $[n]:=\{1,\dots,n\}$. So for example if $\pi=(\{1,3,5\},\{2\},\{4\})$ and $\pi'=(\{1,3\},\{2\})$, then $Coag(\pi,\pi')=(\{1,3,4,5\},\{2\})$. The partition $\pi'$ 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 $\pi$ of $\mathbb{N}$ is a set of disjoint subsets $\{\pi_i\}_{i=1}^\infty$ of $\mathbb{N}$ such that $\bigcup_i \pi_i=\mathbb{N}$. We arrange these sets $\pi_i$ in the order of their least element, so that $\inf \pi_1 < \inf \pi_2< \dots$, and if there are only finitely many subsets, we trail the sequence with emptysets, e.g. $(\{1\}, \mathbb{N}\backslash \{1\},\emptyset,\dots)$. Denote the set of partitions of $\mathbb{N}$ by $\mathcal{P}_\infty$.

Notice that each $\pi \in \mathcal{P}_\infty$ induces an equivalence relation $\buildrel \pi \over \sim$ on $\mathbb{N}$ by $i \buildrel \pi \over \sim j$ if and only if $i$ and $j$ belong to the same block of $\pi$. Now let $\sigma$ be a permutation of $\mathbb{N}$, and we define a partition $\sigma \pi$ by saying that $i$ and $j$ are in the same block of $\sigma \pi$ if and only if $\sigma(i) \buildrel \pi \over \sim \sigma(j)$.

Suppose now that $\pi$ is a random partition. We say that $\pi$ is exchangeable if for each permutation $\sigma$ which changes finitely many elements, we have that $\sigma\pi$ has the same distribution as $\pi$.

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.