Three classes of transition rates
Three distinct classes of random combinatorial structures are called assemblies, multisets, and selections by Arratia and Tavare. We next show how these three types generate three different types of stationary probability distributions.
10.2.1 Selections
Let N(n, a) denote the number of distinct configurations compatible with the partition vector a with
In closed models, the total number of agents
or basic units is fixed at n. Perhaps the simplest and best-known model of agents (in this case particles) separating into two clusters (two urns) is the simple birth-and-death process or Ehrenfest (urn) model found in elementary probability or physics textbooks. See Kelly (1979, Sec. 1.4), or Costantini and Garibaldi (1979) for the urn model. In Aoki (1996a, p. 140), it is used as a basis to build a binary choice model in which each of n agents chooses one of two alternatives subject to aggregate externalities, that is, feedback effects of choices made by all the agents taken together. In this example, there are only two clusters, where ak = 1 and an-k = 1 for k = 0, 1,..., n, and cluster sizes change at most by one in a small time interval. The transition rates are specified by
and
where λ and μ are positive parameters. The graph of this simple randomwalk model is a tree, and the model satisfies the detailed-balance conditions (Kelly 1979, Lemma 1.5). Hence, the process has a steady-state probability distribution, obtained by solving the first-order difference equation generated by the detailed-balance conditions
where B is a normalizing constant, determined by the normalization requirement that the probabilities sum to one, and given by
In a slightly more complicated process with K types or categories, consider the entry rate
for 0 ≤ ni ≤ mi, i = 1, 2,..., K, where the state vector is n = (n1, n2,..., nκ).
Here, mi is the maximum number of agents that can occupy a type i box, or cluster. For example, it might be that opportunities that open up in some specific sector can be taken up by at most mi firms. A similar interpretation is possible in declining sectors of the economy where no more capacity is being added but some may be being, dismantled. See our discussion of multisets in the next subsection.The exit rate is
i = 1, 2,..., K. The detailed balance conditions holds, 
id="Picutre 501" class="lazyload" data-src="/files/uch_group31/uch_pgroup304/uch_uch7235/image/image501.jpg">
10.2.2 Multisets
The next class of random combinatorial structures is called multisets in the combinatorics literature; see Bollobas (1985).6
We first discuss the equilibrium distribution using the empirical distribution, that is, by specifying transition rates in terms of n. Then, we describe the distribution in terms of partition vectors.
Suppose that there are K types of agents and n = n1 + ∙ ∙ ∙ + nκ, where ni is the number of agents of type i. Agents may change their types as time passes. Assume that the relevant transition rates are given by the entry and exit probability intensities, simple in the sense of Kingman (1969), that is,
for nk ≥ 0, with the f's all positive, and
Assume also that the transition intensity for changing types or groups is given by
6 A multiset is a function μ on a set with K elements, {y 1, y2,..., yκ }, with natural numbers as values, μ(yi) = ni.
The number ni is called multiplicity of yi in the literature of random graphs.
We may interpret this distribution as a multiset having exactly ni different objects of size i. In multisets, the parameters fj are important in specifying the entry transition rates. The f term or (the term containing f) is the immigration term in the birth-death-with-immigration model. More generally, in economic models, it represents effects that encourage entry and that are independent of the number of agents in the cluster. Such effects may be policy-related, or may represent aggregate effects of choices by agents, that is, some kind of field effects generated by the total patterns of decisions at previous periods in discrete-time models, or of niche effects that affect only some sectors of the economies, not the whole economies.
Kelly (1979, Chap. 7) has one genetic example. In his model, one unit dies at random, that is, with equal probability for each type. This specifies the exit rate as
This unit is replaced with a new units (to keep the total number of units constant), which is chosen at random from the remaining n — 1 units. With probability 1 — u, it is of the same type as the parent that just died. With probability u it is a different type chosen randomly from the remaining K — 1 types. This specifies the entry rate as
This “story” for the transition rate is not important. What is important is that the entry rate is defined to satisfy the requirement that fk goes to zero as K tends to infinity, while Kfk approaches some positive number θ.
In the population-genetics example u goes to zero as n tends to infinity in such a way that n ? u approaches some positive constant θ, that is, Kf approaches θ as n becomes very large. In the economic context, when K becomes large, whatever encouragement or inducement there is to enter a particular type of cluster, f, becomes very small, although the total effect of entering some sector, Kf, remains nonzero. We return to this point when we discuss the Ewens distribution. We provide one example of macroeconomic business cycles later in Section 10.5.As in selections, we can describe the resulting patterns in terms of partition vectors. Let mi be the number of objects of size i in the multisets. Then the number of configurations is given by
where the binomial coefficient counts the number of ways ai indistinguishable balls can be put into mi identical (or delabeled and hence indistinguishable) boxes.7 For example, this happens in the Bose-Einstein allocation or statistics; see Aoki p. 13).
We next sum the numbers of configurations: 
10.2.2.1 Capacity-limited processes
In some circumstances, an opportunity opens up in some submarkets and is taken up by several firms, or by only one firm, as described in Sutton (1997). In such cases, we think of boxes, that is, types, which at most a few economic entities can occupy - say, one, when the capacity of the type is one. This reminds one of Fermi-Dirac allocations or statistics.
Such capacity-limited processes may be modeled in our multiset entryrate specification by taking integer fk negative. As an example, suppose that w(n, n + ek) = ck(nk - d), with some d > 0.
Recalling the parallels with conditional probabilities,
where the denominator is there for normalization. Writing this expression as (d — n)∕(Kd — n) with d ≥ nk and Kd — n > 0, we arrive at the capacitylimited exit rate. The equilibrium distribution is a hypergeometric distribution.
10.2.3 Assemblies
To understand this expression, recall that the number of ways to partition the
for the number of permutations of size n, having cyclical products specified by the partition vector, in the above expression.
10.2.3.1 Internal configurations of assemblies
Suppose that subsets or blocks of size i can be in one of mi distinct configurations or structures. We say that blocks have structure M with the exponential generating function
The n set has a compound structure, 5(M), when it is split into parts and each part has structure of type M. van Lint and Wilson (1992) count the number of internal structure of the n-set as follows. (At the end of this section we discuss an example of Stirling numbers of the second kind, 5(n, k), which is the number of partitions of [n] with k blocks.)
For some integer-valued function f (i) such as f (i) = mi, where mi is the number of labeled (that is, distinguishable) structures on a set of size i, let its
where the summation is over all partitions with the same partition vector a, and define the exponential generating function of this sequence
Finally, let
Then, we have
This is in van Lint and Wilson (1992, Theorem 14.2), and can also be proved by direct calculation of G [M(x)]:
By comparing the coefficients of xn/n! we can express h(n) in terms ofthe m s:
The right-hand side of the expression for G [M(x)] is
Wherewewriteforconvenience m(i) = mi,and the inner summation is over the 
where c(a) is the number of distinct k-tuples (b1,..., bk) with exactly the same partition vector a, that is,
Therefore, the coefficient of
is given by N(n, a) of the theorem.
This recursion relation is obtained in another way in Section A.5.
10.3