Home Education

Balanced triangular urn models

Using the scheme of Flajolet, Dumas and Puyhaubert (2005), we describe urns with two types of colored balls, black and white. The balls may be interpreted as sectors or innovations. The colors of balls represent different kinds of sectors or innovations. Actual interpretations are quite flexible.

We show that this urn has a number of black balls, say, that are nonself-averaging.

The urn model is described in terms of replacement matrix M. Specifically, we use a 2 X 2 triangular matrix M, with elements m11 = a > 0, m12 = b — a, m21 = 0, and m 22 = b.

This matrix M specifies that, if a black ball (ball of type 1) is drawn, it is returned to the urn together with a additional black balls, and (ba) white balls. If a white ball (ball of type 2) is drawn, then it is returned to the urn together with b white balls. No black ball is added in this case. The replacement matrix M is triangular. The urn is called balanced because the two row sums of M are equal (both sums are b). It means that the total number of balls in the urn is the same regardless of the color of the balls drawn.

We show below that the stochastic process described by this urn model is non-self-averaging. This feature is caused by the fact that the generating mechanism, that is, the mix of balls of two types, is path- dependent for the same reason as the Poisson-Dirichlet model in the preceding section. Note that in this model the ratio of black and white balls is path dependent, and varies endogenously. The number of balls of each type being put into the urn clearly depends on the way the two types of ball have been drawn in the past.

Suppose that there are r black balls and s white balls after n draws. This composition of the types of ball is represented by a monomial as urvs. Then, there are altogether a0 + b0 + b X n balls in the urn, where a0 and b0 are the numbers of initial black and white balls. Recall that the urn is balanced. Now, with r black balls in the urn, there are r ways of picking a black ball, and each such draw results in a additional black balls and ba additional white balls.

Therefore, after a draw of a black ball, the monomial urv s is transformed into rur+avs+b—a. Here variables u and v are dummy variables or place markers to carry information on the numbers of black and white balls.

Likewise, a draw of a white ball changes the monomial into survs+b—a. This evolution is represented by the operator Г:

All possible compositions of this urn at time n are represented by a polynomial in u and v, fn(u,v). Using the operator Г defined above, we have

By defining the exponential generating function

we obtain its first-order partial differential equation

This equation can be solved by the method of characteristics (see Aoki, 2002, A.1), for examples). The partial differential equation above is converted into a set of ordinary differential equations

and

Eliminating dt from the above, we obtain

The equation for v can be integrated directly. Then the other equation is integrated, yielding two constants of integration. The general solution is a function of these two constants of integration. To be concrete, suppose that a = 1 and b = 2. We then obtain the first integral as follows:

and

Hence

where

With this generating function, we can obtain the probability distribution of Xn, the number of black balls at time n. Note that, because the urn is balanced, and the total number of balls at n is not random, once we know the number of black balls we automatically know the number of white balls as well. Puyhaubert (2003) thus establishes the result that Xn is non-self-averaging. It is noted above that Mittag-Leffler function ga (x) has the property that its pth moment is given by

for p > -1.

As we have seen in the previous section, we can show that CV(Xn) remains positive even if n approaches infinity, that is, it is non-self-averaging.

Proposition: The number of black balls in the balanced triangular urn model is non-self-averaging.

Janson (2006) examines triangular urns that are not balanced. Specifically, Janson (2006, th. 1.3) derives that, when the replacement matrix consists of m1tl = a = c + d, щ 2 = c, m21 = 0, and m22 = d he obtains the convergence in distribution

where Xn is the number of black balls, n is the number of drawings, and W has a generalized Mittag-Leffler distribution.

By identifying the two parameters в nd a in the PD (a, U) in the following way

and

where we can observe that these two Mittag-Leffler moment expressions are the same as the random variable L in the two-parameter Poisson- Dirichlet model presented above. This fact means that the two distributions are identical beacuse the moments of Mittag-Leffler distributions uniquely determine the distribution (Bingham, Goldie and Teugels (1987, p. 391). Janson (2006, th. 1.3) shows that, depending on parameters of

the replacement matrix, namely, a,c and d, Xn, the number of black balls, becomes non-self-averaging. Puyhaubert (2005) has explicit expressions for the first two moments of Xn, from which it is clear that Xn is not selfaveraging.

We can summarize this analysis as follows:

Proposition: In non-balanced triangular urn models, depending on the values of parameters, non-self-averaging emerges. Non-self-averaging is generic in the sense that a set of parameters for which non-self-averaging emerges is not of measure zero.

 Related topics