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 $\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.

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.