# 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 *m _{11} *

**=***a*

*0, m*

**>**_{12}= b —

*a,*m

_{21}= 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 *(b* — *a*) 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 *u ^{r}v^{s}.* Then, there are altogether

*a*

_{0}*b*

**+**_{0}+

*b*

**X***n*balls in the urn, where

*a*and b

_{0 }_{0}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

*b*—

*a*additional white balls.

Therefore, after a draw of a black ball, the monomial u^{r}v ^{s} is transformed into *ru ^{r}+^{a}v^{s}+^{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 *su ^{r}v^{s}+^{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, *f _{n}(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 ****X _{n},**

**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**

**X**_{n}**is non-self-averaging. It is noted above that Mittag-Leffler function**

**g**_{a}**(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(X _{n})**

**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 ****m _{1tl} = a = c + d**

**,**

**щ**

_{2}=

**c****, m**

_{21}= 0, and m_{22}=

**d****he obtains the convergence in distribution**

**where ****X _{n}**

**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, X _{n},* the number of black balls, becomes non-self-averaging. Puyhaubert (2005) has explicit expressions for the first two moments of

*X*from which it is clear that

_{n},*X*is not selfaveraging.

_{n}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.