A.8 Exchangeable random partitions

To discuss a large number of agents forming clusters of various sizes, the no­tion of exchangeable random partitions, which is due to Kingman (1978a,b), is useful. We follow Zabell (1992) in describing the notion.

A.8.1 Exchangeable random sequences

Let X₁, X ₂,... be an infinite sequence of random variables taking on k discrete values, c₁, c₂,..., c_κ, say. These are possible categories or types of decisions or choices by agents (or cells, in the literature on occupancy numbers in prob­ability theory) into which the outcomes or realizations of the sequence are classified.

The sequence is said to be exchangeable if for every n, the cylinder set probabilities

are invariant under all possible permutations of the subscripts of Xs.³ In other words, two sequences have the same probability if one is a rearrangement of the other.

Let n_i denote the number of times the i th type occurs in the sequence. The vector n = (n₁, n₂,..., n_k) is called the frequency vector. The vector n/N is known as the empirical distribution in statistics. Note that given any two sequences, one can be obtained from the other if and only if the two sequences have the same frequency vector or empirical distribution.

The observed frequency counts nj = nj(X₁, X₂,..., X_n) are sufficient statistics, in the language of statistics, for the sequence {X₁, X₂,..., X_n}, be­cause probabilities conditional on the frequency counts depend only on n, and are independent of the choice of the exchangeable probability Pr.

By exchangeablity, each of the sequences having the same frequency vector is equally probable. There are N!/n₁!n₂! ∙ ∙∙ n_k! such sequences, and consequently

We have the de Finetti representation theorem for exchangeable sequences (de Finetti 1974, 1975): if an infinite sequence of k-valued random variables X₁, X₂,... is exchangeable, then the infinite limiting frequency

exists almost surely; and if

denotes the distribution of this limiting frequency, then

To apply the de Finetti theorem, we must choose a specific prior or mixing measure, dμ. One way is to follow Johnson et al. (1997) and postulate that all These subscripts may be thought of as time indices or as giving the order in which samples are taken.

ordered k-partitions of N are equally likely. This postulate uniquely determines d μ to be

a flat prior.

Less arbitrary is Johnson's sufficientness postulate^[20]

if Pr(Xi = c₁,..., X_n = c_N) > 0 for all c's. This formula states that in pre­dicting that the next outcome is c_i, n_i is the only relevant information contained in the sample. Zabell shows that Johnson's sufficientness postulate implies that whereis the parameter of the symmetrical Dirichlet prior, which is

the mixing measure dμ.

A.8.2 Partition exchangeability

In economic applications such as multiple-agent models of stock markets, groups of agents of different types interact. We face exactly the same problem that confronted statisticians in dealing with the so-called sampling-of-species problem. Sometimes this problem is referred to as the ecological problem in the emerging literature on multiagent or agent-based modeling in economics.

Suppose we take a snapshot of all the agents in the market - a sample of size n at a point in time and observe all the different trading strategies in use. Some or most strategies (types of agents) have been seen in such snapshots or samples taken earlier. There may be new ones not so far observed, however. As Zabell clearly explains, this is not the problem of observing an event to which we assign 0 probability, that is, an event whose probability we judge to be 0. Rather, the problem is observing an event whose existence we did not even previously suspect. A new strategy is invented, or new type of agents are born, and so on. Zabell calls it the problem of unanticipated knowledge. To deal with this problem we need Kingman's construction of exchangeable partition.

A probability function P is partition-exchangeable if the cylinder-set prob­abilities P(X₁ = e₁, X₂ = e₂,..., X_n = e_N) are invariant with respect to per­mutations of the time index and the category index. For example, suppose

you roll a die, and you obtain a sample {5, 2, 1, 5, 4, 4, 6, 4, 6}. Here, K = 6. Rearrange the time indices, i.e., the samples, into a standard descending order of observed frequency of each face of the die, {4, 4, 4, 5, 5, 6, 6, 1, 2}, and then perform the category permutation (1, 2)(3, 5)(4, 6), that is, 1 → 2 → 1, 3 → 5 → 3, 4 → 6 → 4. By definition, if P is partition-exchangeable we have

P(5, 2, 1, 5, 4, 4, 6, 4, 6) = P(6, 6, 6, 3, 3, 4, 4, 2, 1).

Define the frequencies of the frequencies (called abundances in the population-genetics or sampling-of-species literature) by what Zabell calls the partition vector a = (a₁, a₂,... a_N), where a_r is the number of n.j that are ex­actly equal to r.⁵ In the above example, the original sample has the frequencies n₁ = 1, n₂ = 1, n₃ = 0, n₄ = 3, n₅ = 2, n₆ = 2:

n = (1, 1, 0, 3, 2, 2) = 0¹1²2²3¹,

where the last expression is the notation of Andrews (1971) used to indi­cate cyclic products of permutations with a_i cycles of size i. In this example [a₁ = 2, a₂ = 2, a₃ = 1, a₄ = a₅ = ∙ ∙ ∙ = a₁₀ = 0. Note also that a₀ = 1.

The partition vector plays the same role relative to partition-exchangeable sequences that the frequency vector plays for exchangeable sequences. Two sequences are equivalent, in the sense that one can be obtained from the other by a permutation of the time set and a permutation of the category set, if and only if the two sequences have the same partition vector. We can thus alternatively characterize partition exchangeability by the fact that all sequences having the same partition vector have the same probability. Probabilities conditional on the partition vector are independent of P.

We formally define that a random partition is exchangeable if any two par­titions π₁ and π₂ having the same partition vector have the same probability:

Since partition-exchangeable sequences are exchangeable, they can be repre­sented by dμ on the K-simplex Δ_k. To prepare our way for letting K become infinite, we use the order statistics. Denote by Δ_k the simplex of the ordered probabilities

In the case of the partition-exchangeable sequences, the conditional probability

5

Kingman named it differently because he was working in population genetics.

becomes

There are K! permutations of the integers {1, 2,..., K}. To every permuta­tion there corresponds the set defined by

Example. Given a sample of size 10, taken in the order 6, 3, 4, 2, 3, 1, 6, 2, 2, 3, we have a partition

Its partition vector is a = (2, 1, 2, 0, 0,..., 0). This indicates that there are two singletons, one cluster with two numbers, and two clusters with three elements each, and the others are empty. The sumgives the total number of

clusters, that is, five different groupings have been observed in this sample.

By the exchangeability of the underlying sequence, permuting time indices produces a new sequence with the same frequency vector n, hence the same partition vector a.

We state the Kingman representation theorem for the record. There is a unique d μ on V,the infinite simplex of all ordered defective probability vectors, such that

where dμ(p) is a Poisson-Dirichlet process.

Instead of the POne agent of the latter type is lost, causing the number of types represented by k - 1 agents to be a_k-1, and the number with k agents to be a_k.