A.2 Urn models and associated Markov chains

A.2.1 Polya's urn

A two-type Polya urn is an urn containing balls of two colors, b black and y yellow balls, say. Each time a ball is drawn, it is returned to the urn to­gether with c balls as the same color the one just drawn.

Note that any other outcome of the first n draws with m black and l yellow balls drawn has the same probability, because the factors in the denominator increases by c per draw, and the numerators are just permutations of the ones shown above. The fraction of black balls after the nth draw, X_n, is a martingale

A.2.2 Hoppe’s urn

An application of this to a model with a partition vector as a state vector is given in Hoppe (1987). Suppose that we wish to compute the expected value of the number of types with exactly j agents, denoted by aj. In the context of size distribution of firms, this is the number of firms in category j, i.e., the number of firms with j units, given the total of n units in the model. Draw the first sample and label it type 1. Its future occurrences in the sample are described by a two-type Polya urn just discussed. See also Appendix A.9.2. The probability that type 1 is observed i times in a sample of size n is

where S₁ is the number of times type 1 units are observed. There are ia_i type 1 units in the total n units; hence

By integration

where (n)_i := n(n - 1) ∙ ∙ ∙ (n - i + 1).

Hoppe (1984) also shows how to derive the Ewens sampling formula from a generalized Polya urn. Consider an urn that contains one black ball of weight θ > 0, and various numbers of nonblack balls, each of weight one. Initially the urn contains only the black ball. At the nth drawing, a ball is drawn at random in proportion to its weight. If a nonblack ball is drawn, then it is returned together with one more ball of the color drawn. If the black ball is drawn, then the black ball is returned together with one ball of a color not previously drawn, that is, this returned ball has a new color. This event occurs with probability θ/(θ + n). This is the entry probability for a ball of a color not previously observed. For convenience of reference label the nonblack colors as 1, 2,..., K in the order of appearance when there are K nonblack colors, that is, the black ball has been drawn K times by the end of the nth drawing.

Define the random variable Y_n = i when a ball of color i is returned after the nth drawing, 1 ≤ i ≤ K. A partition of n balls into K colors is the same as an allocation of n balls into K labeled boxes.

Let n_i be the number of balls of color i, 1 ≤ i ≤ K. We note that n₁ + n₂ + ∙ ∙ ∙ + n_K = n. Here, we have a random partition of a set {1, 2,..., n} into K subsets. The partition vector a = (a₁, a₂,..., a_K) is such that a_i is the number of colors with exactly i balls, or the number of times i appears in {n₁, n₂,..., n_K}. The sequence of random variables {Y_k}J"=₁ partitions the set {1, 2,..., n} randomly.

because the black ball is drawn K times. In between, n_i - 1 nonblack balls are drawn, and the denominator has the factors increasing by one by each drawing.

In total then, there are

many sample paths consistent with the partition vector, where the first factor is there because there are K! disjoint classes of permutations given by the first integer and these are all equally likely. When the above is multiplied by the sample probability given above, we obtain the Ewens sampling formula.

A.2.3 Markov chain associated with the urn

Hoppe (1987) associates a Markov chain with the partition process {∏_n} having one-step transition probabilities

from a partition vector a of dimension r to a partition vector b of dimension r + 1, with ∏₀ the empty partition.

Transition probabilities are specified to make a familiy of distributions on partitions satisfy the Kingman consistency relation. Define