Partition exchangeability

We follow Zabell (1992) in describing the notion of exchangeable random partitions, which is due to Kingman (1978a, 1978b). In economic applica­tions such as multiple-agent models of stock markets, we encounter exactly the same problem faced by statisticians in dealing with the so-called sampling- of-species problem.

problem in the emerging literature on multiagent or agent-based modeling in economics. 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 when we observe an event whose existence we did not even previously suspect. A new strategy is invented, a new type of agents is born, new goods become available, and so on. Zabell calls this the problem of unanticipated knowledge. Suppose we take a snap­shot of all the agents in a market or take a sample of size n at a point in time, and observe all different trading strategies in use by agents in the snapshot or in the sample. Some or most strategies have been seen in past snapshots or samples. There may be new ones that have not so far been observed, how­ever. To deal with this problem we need Kingman's construction of random partition exchangeability. A probabilityfunction P is partition-exchangeable if

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.

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 index, i.e., the samples, into the stan­dard form of descending order of observed frequency of each face of the die: {4, 4, 4, 5, 5, 6, 6, 1, 2}. Then perform the category permutation (1, 2) (3, 5) (4, 6), that is, 1 → 2 → 1, 3 → 5 → 3, 4 → 6 → 4. Thus, in the partition­exchangeable setup, we have

Define the frequencies of the frequencies (called abundances in the population-genetics or sampling-of-species literature) by the partition vector a = (a₁, a₂,..., a_n), where a_r is the number of n.j that are exactly equal to r. This vector is an example of state variables of second specification according to Sachkov, mentioned in Chapter 1. In the above example, the original sample has the frequencies n₁ = 1, n₂ = 1, n₃ = 0, n₄ = 3, n₅ = 2, n₆ = 2; hence the frequecy vector is

where the last expression is in the notation of Andrews (1971), originally used to indicate cyclic products of permutations with a_i cycles of size i. Here

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, just as probabilities conditional on the frequency vector (empirical means) are inde­pendent of P.

Definition. We formally call a random partition exchangeable if any two partitions π₁ 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.

In the case of the partition-exchangeable sequences, the conditional proba­bility becomes

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

The map of the probability vector into the vector of probabilities with per­muted indices defines a homeomorphism of Δ_{k σ} onto ΔK. This map can be used to transfer dμ on ΔK to the subsimplex Δ_kσ. See Hansen (1990) or Donnelly and Joyce (1989).

In the sampling-of-species context, such as taking a snapshot of a market at a point in time and counting the numbers of agents by the types of strategies they are using at that point in time, the relevant information received is an exchangeable random partition of N := {1, 2,..., N}, where N is the total number of agents in the market at that time. Individual types, algorithms, or categories have no significance. We observe the first type, then possibly later

the second, and so on. We therefore partition N as

2.5