You are currently browsing the tag archive for the ‘exchangeable’ 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.

Read the rest of this entry »

Advertisements

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.

Read the rest of this entry »