数理解析研究所講究録 1308 巻 2003 年 29-38

29
Generalized P\’olya urn models
and related distributions
統計数理研究所 井上 潔司 ( Kiyoshi Inoue )The Institute of Statistical Mathematics
Abstract. In this paper, we consider aPolya urn model containing balls of $m$ different labels
under ageneral replacement scheme, which is characterized by an $m\cross m$ addition matrix of
integers other than non-negativity. This
integers without constraints on the values of theseurn model includes some important urn models treated before. By amethod based on theprobability generating functions, we consider the exact joint distribution of the numbers of balls
draws. As aspecial case, for $m=2$ , thewith particular labels which are drawn within
univariate distribution, the probability generating function and the expected value are derived
exactly.
We present methods for obtaining the probability generating functions and the expected values
for all exactly, which are very simple and suitable for computation by computer algebra systems.
The results presented here develop ageneral workable framework for the study of P\’olya urn
models and attract our attention to the importance of the exact analysis. Our attempts are very
useful for understanding non-classical urn models. Finally, numerical examples are also given inorder to illustrate the feasibility of our results.
$m^{2}$$n$$n$

Key words and phrases: Polya urn, replacement scheme, addition matrix, probability
generating functions, expected value.

1Introduction
Urn models have been among the most popular probabilistic schemes and have received
considerable attention in the literature (see Johnson, Kotz and Balakrishnan (1997),
Feller (1968) . The Polya urn was originally applied to problems dealing with the spreadof acontagious disease (see Johnson and Kotz (1977), Marshall and Olkin (1993)).
balls labeled
We describe the Polya urn scheme briefly. From an urn containing
balls labeled 2, aball is drawn, its label is noted and the ball is returned to
1andthe urn along with additional balls depending on the label of the ball drawn; If aballballs labeled $j(j=1,2)$ are added. This scheme islabeled $i(i=1,2)$ is drawn,$)$$\alpha_{1}$$\alpha_{2}$$a_{ij}$characterized by the following$2\cross 2$

addition matrix of integers,$(\begin{array}{ll}a_{11} a_{12}a_{21} a_{22}\end{array})$;whoserows are indexed by the label selected and whose columns are indexed by the label ofthe ball added.
Several P\’olya urn models have been studied by many authors in the various addition
matrices, which generate many fruitful results. The case of the classical Polya urn model$(a_{11}=\mathrm{a}22, a_{12}=a_{21}=0)$ was studied earlier and adetailed discussion can be found, $a_{12}=a_{21}=0$ , Aki and Hirano
in Johnson and Kotz (1977). In the case of
for $i\neq j$,(1988) obtained the Polya distribution of order . In the case of$(i,j=0,1, \ldots, m)$ , Inoue and Aki (2000) considered the waiting time problem for the firstoccurrence of apattern in the sequence obtained by an $(m+1)\cross(m+1)$ Polya urn scheme,$a_{11}=\mathrm{a}22$$k$$a_{\dot{|}i}=c$$a_{\dot{|}j}=0$

30
In the case of $a_{11}=022$ , $a_{12}=a_{21}$ , Friedman (1949) obtained the moment generating
function of the total number of balls with aparticular label remaining in the urn afterdraws; Friedman’s urn can be used to model the growth of leaves in recursive trees (seealso Mahmoud and Smythe (1991) . In the case of $a_{11}+a_{12}=a_{21}+a_{22}$ , Bagchi and Pal(1985) showed an interesting example of Polya urn scheme applied to data structures incomputer. (Gouet $(1989,1993)$ corrected some of the statements made by Bagchi andP\’olya urn scheme (constant row sums allowing negative entries on
Pal (1985) . In a
the diagonal, but having several constraints on the eigenvalue structure), Smythe (1996)
considered acentral limit theorem.
One interest has been focused on the exact distribution of the total numbers of ballswith particular labels remaining in the urn after draws, or the exact distribution of
the numbers of balls with particular labels which are drawn within draws from theurn. Their derivation involves acombinatorial method of counting paths representing arealization of the urn development.
For along time, most investigations have been made under the special structure of
the constant addition matrix with constant row sums, which implies asteady linear
growth of the urn size. The reason for the imposition of this constraint is mathematicalconvenience; Urn schemes where the constraint is imposed are generally much simpler
to analyze than those where it was not imposed.
Recently, Kotz, Mahmoud and Robert (2000) attempted to treat aP\’olya urn model
containing 2different labels according to ageneral replacement scheme, and pointed outthat no constraint case is considerably more challenging even incase. That is, theexact distribution of the number of balls with aparticular label which are drawn withindraws is rather convoluted and such an exact distribution is rather unwieldy for large
for numerical computation.
Our purpose in the present paper is to develop ageneral workable framework for theexact distribution theory for P\’olya urn models mentioned before and to emphasize theimportance of the exact analysis. The approach is to solve asystem of equations ofconditional probability generating functions (p.g.f.’s). Then, the probability functions
and moments are derived from an expansion of the solution regardless of whether or not
the constraint is imposed.
In this paper, aPolya urn model containing balls of $m$ different labels and characterized by ageneral replacement scheme is considered, which include some importantmodels treated before. We consider the exact joint distribution of the numbers of ballswith particular labels which are drawn within draws. As aspecial case, aunivariate
distribution is derived from aPolya urn model containing balls of 2different labels.
For the derivation of the main part of the results, we use the method based on theconditional p.g.f.’s. This method was introduced by Ebneshahrashoob and Sobel (1990),
and was developed by Aki and Hirano $(1993, 1999)$ , Aki, Balakrishnan and Mohanty(1996). The procedure is very simple and suitable for computation by computer algebra
systems. Furthermore, we propose amethod for the P\’olya urn model. It is arecurrence
$n$

$)$

$)$

$p\cross p$

$n$

$n$

$2\cross 2$

$n$

$n$

$n$

31
for obtaining the expected values for all , which is derived from the system of equations. ’s.
of conditional
The rest of this paper is organized in the following ways. In Section 2, aPolya urn
model containing balls of $m$ different labels is introduced, which is characterized by thegeneral replacement scheme. As aspecial case, aunivariate distribution is derived fromaPolya urn model containing balls of 2different labels. We give amethod for the Polyaurn models. It is arecurrence for obtaining the expected values for all . In Section 3,
numerical examples are given in order to illustrate the feasibility of our main results.
$n$$\mathrm{p}.\mathrm{g}.\mathrm{f}$$n$2The models
In this section, we consider aPolya urn model characterized by an $m\cross m$ addition matrix. As aspecial case, for $m=2$ , the univariate distribution, the probability generating
function and the expected value are derived exactly.

2.1

The Polya urn model containing m different labels

balls labeledballs labeled 2, ...,
balls labeled 1,
From an urn containing$m$ , aball is chosen at random, its label is noted and the ball is returned to the urnalong with additional balls according to the addition matrix of non-negative integers,$A=(a_{ij})i,j=1$ , , $m$ , whose rows are indexed by the label of the ball chosen and whose
columns are indexed by the label of the ball added. Always starting with the newly
be asequence
constituted urn, this experiment is continued times. Let , , ,$B=\{1,
2,\ldots,m\}$ . Let
obtained by the above scheme, which take values in afinite set
be subsets, , ,be apositive integer such that $1\leq r\leq 2^{m}-1$ and let
for $i\neq j$ . Then, we define the numbers of balls
andof , where$(i=1, \ldots, r)$ which are drawn within
draws
whose labels belong to the subsets
means the indicator
by $X_{n}^{(i)}= \sum_{j=1}^{n}I_{B}\dot{.}(Z_{j})(i=1, \ldots, r)$ , where
function of the subset .
of the joint distribution
In the sequel, we will obtain the p.g.f.
. Hereafter, we denote the urn composition and the total of theofand $|b|=\alpha_{1}+\alpha_{2}+\cdots+\alpha_{m}$ , respectively. We
balls in the urn by $b=$
. Needless to say,row of the addition matrix by $a_{i}=$denote the$(i=1, \ldots, m)$ and $|b|\neq 0$ are assumed throughout this paper.
after $\ell(\ell=0,1, \ldots, n)$
Suppose that we have an urn composition $b=$
the p.g.f. of the conditional distribution of thedraws. Then, we denote by$(i=1, \ldots, r)$ which are drawn
numbers of balls whose labels belong to the subsets
within $(n-\ell)$ draws, where $t=(t1, \ldots, t_{r})$ .
$\alpha_{m}$$\alpha_{2}$$\alpha_{1}$$\ldots$$Z_{1}$$n$$Z_{2}$$B_{1}$$r$$B$$\ldots$$B_{2}$$Z_{n}$$\ldots$$B_{r}$$B_{i}\neq B_{j}$$B_{i}\neq\emptyset$$n$$B_{i}$$I_{B}\dot{.}(\cdot)(i=1, \ldots, r)$$B_{i}$$E[t_{1}^{X_{n}^{(1)}}t_{2}^{X_{n}^{(2)}}\cdots t_{r}^{X_{n}^{(r)}}]$$(X_{n}^{(1)},X_{n}^{(2)}, \ldots, X_{n}^{(r)})$$(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{m})$$A$$i\mathrm{t}\mathrm{h}$$(a_{i1},a_{i2}, \ldots, a_{im})$$\alpha_{i}\geq 0$$(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{m})$$\phi_{n-\ell}(b;t)$$B_{i}$

Theorem 2.1 From the definitions of $\phi_{n-\ell}(b;t)(\ell=0,1, \ldots, n)$ , we have the following

32
system of the equations;
(2.1)

,

$\phi_{n}(b;t)=\sum_{i=1}^{m}\frac{\alpha_{i}}{|b|}t^{\mathrm{I}_{\mathrm{B}}(i)}\phi_{n-1}(b+a_{i};t)$(2.2)$\phi n-\ell(b;t)=\sum_{i=1}^{m}\frac{\alpha_{i}}{|b|}t^{\mathrm{I}_{\mathrm{B}}(i)}\phi n-\ell-1(b+a_{i;}t)$(2.3)$\phi_{0}(b;t)=1$

where,,$\ell=1,2$,$\ldots$, $n-1$ ,,$t^{\mathrm{I}_{\mathrm{B}}(i)}=t_{1}^{I_{B_{1}}(i)}t_{2}^{I_{B_{2}}(i)}\cdots t_{r}^{I_{B_{r}}(i)}$.

Proof. It is easy to see that $\phi_{0}(b;t)=1$ by the definition of the p.g.f.. Suppose that theurn composition is $b=$
after $\ell(\ell=0,1, \ldots, n-1)$ draws. Then, the p.g.f.
of the conditional distribution of the numbers of balls whose labels belong to the subsets$Bj$ $(j=0, \ldots, r)$ which are drawn within $(n-\ell)$ draws is $\phi_{n-\ell}(b;t)(\ell=0,1, \ldots, n-1)$.
We should consider the condition of one-step ahead from every condition. Given thecondition we observe the $(\ell+1)$ -th draw. For every $i=1$ , , $m$ , the probability that wedraw the ball labeled \’i is. If we have the ball labeled $(i=1, \ldots, m)$ , then thep.g.f. of the conditional distribution of the numbers of balls whose labels belong to the$(j=0, \ldots, r)$ which are drawn within $(n-\ell-1)$ draws issubsets$(\ell=0,1, \ldots, n-1)$ . Therefore, we obtain the equations (2.1) and (2.2).
$(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{m})$$\ldots$$\alpha_{i}/|b|$$i$$B_{j}$$\phi_{n-\ell-1}(b+a_{\dot{l}};t)$$\square$Example 2.1 Assume that $B=\{1,2,3,4\}$ , $B_{1}=\{2,4\}$ , $B_{2}=\{3,4\}$ , $t=(t_{1}, t_{2})$and the addition matrix is equal to thezero matrix. Suppose that we have an
urn composition
after $\ell(\ell=0,1, \ldots, n)$ draws. Then, we denote by
the p.g.f. of theof the numbers of balls whose labels
belong to the subsets Bi,B2 which are drawn within $(n-\ell)$ draws. Then, we have thefollowing system of the equations;$4\cross 4$$b=(\alpha_{1}, \alpha_{2}, \alpha_{3}, \alpha_{4})$$\phi_{n-\ell}(b;t)$(2.4)$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{b}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\backslash$$\phi_{n-\ell}(b;t_{1},t_{2})$$=$$( \frac{\alpha_{1}}{|b|}+\frac{\alpha_{2}}{|b|}t_{1}+\frac{\alpha_{3}}{|b|}t_{2}+\frac{\alpha_{4}}{|b|}t_{1}t_{2})\phi_{n-\ell-1}(b;t_{1},t_{2})$$\ell=0,1$(2.5)$\phi_{0}(b;t_{1}, t_{2})$$=$$\ldots$, $n-1$ ,1.

Under an initial urn composition
(2.6)

,

,

$b_{0}=(2\cdot 1)\alpha_{02},$ $\alpha_{03},$$\alpha_{04})$, we get$\phi_{n}(b_{0;}t_{1}, t_{2})=(\frac{\alpha_{01}}{|b_{0}|}+\frac{\alpha_{02}}{|b_{0}|}t_{1}+\frac{\alpha_{03}}{|b_{0}|}t_{2}+\frac{\alpha_{04}}{|b_{0}|}t_{1}t_{2})^{n}$In this example, if the labels 1, 2, 3, 4are regarded as $(0, 0)$ , $(1, 0)$ , $(0, 1)$ , $(1, 1)$ , respectively, the equation (2.6) is the p.g.f. joint distribution of the number of balls withthe first label 1and the number of balls with the second label 1which are drawn withindraws. The distribution is called the bivariate binomial distribution (see Kocherlakota(1989), Marshall and Olkin (1985) .
$n$

$)$

33
2.2

The Polya urn model containing 2different labels

As aspecial case, for $m=2$ , we study the Polya urn model containing 2different labels.
.
Assume that $B=\{1,2\}$ , $B_{1}=\{2\}$ and $A=(a_{ij})i,j=1,2$ . Let$\ell(\ell=0,1,\ldots,n)$draws.
after
Suppose that we have an urn composition
Then, we denote by
the p.g.f. of the conditional distribution of the numberof balls labeled 2which are drawn within $(n-\ell)$ draws. From Theorem 2.1, we havethe following Corollary 2.1.
$\mathrm{Y}_{n}=\sum_{i=1}^{n}I_{B_{1}}(Z_{i})$$b=(\alpha_{1}, \alpha_{2})$$\psi_{n-\ell}(b;t_{1})$Corollary 2.1 From the definitions of $\psi_{n-\ell}(b;t_{1})(\ell=0,1, \ldots, n)$, we have the following
system of the equations;

,

(2.7)

$\psi_{n}(b;t_{1})=\frac{\alpha_{1}}{|b|}\psi_{n-1}(b+a_{1}; t_{1})+\frac{\alpha_{2}}{|b|}t_{1}\psi_{n-1}(b+a_{2};t_{1})$(2.8)$\psi_{n-\ell}(b;t_{1})=\frac{\alpha_{1}}{|b|}\psi_{n-\ell-1}(b+a_{1}; t_{1})+\frac{\alpha_{2}}{|b|}t_{1}\psi_{n-\ell-1}(b+a_{2}; t1)$

, $\ell=1,2$ ,$\ldots$, $n-1$ ,(2.9) $\psi_{0}(b;t_{1})=1$ .
$\square$We will solve the system of the equations (2.7), (2.8) and (2.9) under an initial urn
composition. First, we note that the above equation (2.7) can be written
in matrix form as$b_{0}=(\alpha_{01}, \alpha_{02})$$\psi_{n}(b_{0;}t_{1})$$=$$\frac{\alpha_{01}}{\alpha_{01}+\alpha_{02}}\psi_{n-1}(b_{0}+a_{1}; t_{1})+\frac{\alpha_{02}}{\alpha_{01}+\alpha_{02}}t_{1}\psi_{n-1}(b_{0}+a_{2}; t_{1})$$=$$( \frac{\alpha_{01}}{\alpha_{01}+\alpha_{02}}\frac{\alpha_{02}}{\alpha_{01}+\alpha_{02}}t_{1})$$=$$C_{1}(t_{1})\psi_{n-1}(t_{1})$$(\begin{array}{l}\psi_{n-1}(b_{0}+a_{1}\cdot,t_{1})\psi_{n-1}(b_{0}+a_{2}\cdot,t_{1})\end{array})$,,, (say).

Next, for $\ell=1$ , we write the equation (2.8) as$\psi_{n-1}(b_{0}+a_{1}; t_{1})$$=$$\frac{\alpha_{01}+a_{11}}{\alpha_{01}+\alpha_{02}+a_{11}+a_{12}}\psi_{n-2}(b_{0}+2a_{1}; t1)$$+t_{1}\psi_{n-2}(b_{0}+a_{1}+a_{2;}t_{1})\underline{\alpha_{02}+a_{12}}$,$\alpha_{01}+\alpha_{02}+a_{11}+a_{12}$$\psi_{n-1}(b_{0}+a_{2;}t_{1})$$=$$\underline{\alpha_{01}+a_{21}}\psi_{n-2}(b_{0}+a_{1}+a_{2;}t_{1})$$\alpha_{01}+\alpha_{02}+a_{21}+a_{22}$$+ \frac{\alpha_{02}+a_{22}}{\alpha_{01}+\alpha_{02}+a_{21}+a_{22}}t_{1}\psi_{n-2}(b_{0}+2a_{2;}t_{1})$,or, equivalently,$(\begin{array}{l}\psi_{n-1}(b_{0}+a_{1}\cdot,t_{\mathrm{l}})\psi_{n-1}(b_{0}+a_{2}t_{1})\end{array})$$=$$( \frac{\alpha+a}{\alpha_{01}+\alpha_{02}+a_{11}+a_{1,2},0}$.

$\ovalbox{\tt\small REJECT}\alpha+a\alpha_{01}+\alpha_{02}+a_{21}+a_{22}0t_{1})$$\alpha^{1}\frac{\ovalbox{\tt\small REJECT}\alpha+a01+\alpha_{02}+a_{11}+a_{12}^{l}\alpha_{01}+a_{21}}{\alpha_{01}+\alpha_{02}+a_{21}+a_{22}}$$(\begin{array}{l}\psi_{n-2}(b_{0}+2a_{1}t_{1})\psi_{n-2}(b_{0}+a_{1}+a_{2}\cdot,t_{1})\psi_{n-2}(b_{0}+2a_{2}t_{1})\end{array})$.

34
We write $\psi_{n-1}(t_{1})=C_{2}(t_{1})\psi_{n-2}(t_{1})$ . For non-negative integers, let$\ell_{1}$,$\ell_{2}$such that$\ell_{1}+\ell_{2}=$$\mathit{1}$$\psi_{n-\ell}(t_{1})=\{\begin{array}{l}\psi_{n-\ell}(b_{0}+\ell a_{1}\cdot,t_{1})\psi_{n-\ell}(b_{0}+(\ell-1)a_{1}+a_{2}t_{1})\psi_{n-\ell}(b_{0}+(\ell-2)a_{1}+2a_{2}\cdot,t_{1})\vdots\psi_{n-\ell}(b_{0}+\ell_{1}a_{1}+\ell_{2}a_{2}\cdot,t_{1})\vdots\psi_{n-\ell}(b_{0}+\ell a_{2}\cdot,t_{1})\end{array})$.

Then, the system of the equations (2.7), (2.8) and (2.9) can be written in matrix form as$\psi_{n-\ell+1}(t_{1})=C\ell(t_{1})\psi_{n-\ell}(t_{1})$$(\ell=1, \ldots, n)$ , and $\psi_{0}(t_{1})=1(n+1)=(1,1, \ldots, 1)$ ’, where,$1_{(n+1)}$ denotes the $(n+1)\cross 1$ column vector whose components are all unity and$(\ell +1)$ matrix whose
component is given by,denotes the$C_{\ell}(t_{1})$$\ell\cross$$(i,j)\mathrm{t}\mathrm{h}$$\frac{\alpha_{01}+(\ell-i)a_{11}+(i-1)a_{21}}{\alpha_{01}+\alpha_{02}+(\ell-i)(a_{11}+a_{12})+(i-1)(a_{21}+a_{22})}$(2.10) $c_{ij}(\ell; t_{1})=\{$, $j=i,i=1$ ,$\ldots,\ell$,, $j=i+1$ , $i=1$ ,$\frac{\alpha_{02}+(\ell-i)a_{12}+(i-1)a_{22}}{a_{01}+\alpha_{02}+(\ell-i)(a_{11}+a_{12})+(i-1)(a_{21}+a_{22})}t_{1}$0,$\ldots,\ell$,otherwise.

Proposition 2.1 The probability generating functionof and its expected value are given by$\psi_{n}(b_{0;}t_{1})$, the exact distribution$\mathrm{Y}_{n}$$\psi_{n}(b_{0;},t_{1})=C_{1}(t_{1}).C_{2}(t_{1})\cdots$$C_{n}(t_{1})1_{(n+1)}= \prod_{i=1}^{n}C_{\dot{l}}(t_{1})1_{(n+1)}$,$P( \mathrm{Y}_{n}=y)=\sum_{1\leq n_{1}<\cdots<n_{y}\leq n}C_{1}(0)\cdots\dot{C}_{n_{1}}(0)\cdots\dot{C}_{n_{y}}(0)\cdots C_{n}(0)1_{(n+1)}$$E[ \mathrm{Y}_{n};b\circ]=\sum_{i=1}^{n}C_{1}(1)\cdots$ $\dot{C}_{i}(1)\cdots$ $C_{n}(1)1_{(n+1)}$

where,$C.k(t_{1})= \frac{dC_{k}(t_{1})}{dt_{1}}=(.\frac{d\mathrm{q}_{j}(k,t_{1})}{dt_{1}}.)$,,.
$\square$

In asimilar way, under an initial urn composition $b0=$, we can solve
the system of the equations in Theorem 2.1 by virtue of their linearity and obtain thep.g.f.. However, we do not write it due to lack of space.
$(\alpha_{01}, \alpha 02, \ldots, \alpha_{0m})$

Remark 1In this Polya urn model, Kotz, Mahmoud and Robert (2000) derived theexact distribution of
by another approach, and derived the recurrence relation for
the expected value. They also reported that the expected value can be derived from therecurrence relation in a case that the constraint is imposed, whereas the expected value
can not be derived from it in a case that the constraint is not imposed. Then, we present
a useful recurrence for the expected values, as will be shown later$\mathrm{Y}_{n}$

35
2.3

The recurrences for the expected values

In this subsection, we present amethod for the exact analysis, which are very simple and suitable for computation by computer algebra systems. It is arecurrence forobtaining the expected values for all .
$n$

Theorem 2.1 (The Polya urn model containing m different labels); b] say, satisfy the recurrences;(i $=0,$ 1, \ldots r),
The expected values of$X_{n}^{(i)}$$E[X_{n}^{(i)}$(2.11)$E[X_{n}^{(i)} ; b]$$=$$\sum_{j=1}^{m}\frac{\alpha_{j}}{|b|}(I_{B}.\cdot(j)+E[X_{n-1}^{(i)}; b+a_{j}])$(2.12)$E[X_{0}^{(i)} ; b]$

$=$

0,

,

$n\geq 1$, $i=1$ ,$i=1$ ,$\ldots$$\ldots$

, ,
$r$

, .
$r$

It is easy to check the equation (2.12). The equation (2.11) is obtained bydifferentiating both sides of the equation (2.1) with respect to $t_{i}(i=1, \ldots, r)$ and thensetting $t_{1}=\cdots=t_{r}=1$ . The proof is completed.
Proof,$\square$

As aspecial case, for $m=2$ , we consider the Polya urn model containing 2different
labels treated in Section 2.2. Then, from Theorem 2.1, we have the following Corollary
2.2.
Corollary 2.2 (The Polya urn model containing 2different labels)say, satisfies the recurrence;
The expected value of ,$\mathrm{Y}_{n}$$E[\mathrm{Y}_{n};b]$,(2.13)$E[ \mathrm{Y}_{n};b]=\frac{\alpha_{1}}{|b|}E[\mathrm{Y}_{n-1}; b+a_{1}]+\frac{\alpha_{2}}{|b|}E[\mathrm{Y}_{n-1}; b+a_{2}]+\frac{\alpha_{2}}{|b|}$(2.14)$E[\mathrm{Y}_{0;}b]=0$$n\geq 1$,.
$\square$

3Numerical examples
In this section, we illustrate how to obtain the distributions and the expected values
by using computer algebra systems.
Example 4.1 :The Polya urn model containing 4different labels
Assume that $b_{0}=(1,2,1,2)$ , $B=\{1,2,3,4\}$ , $B_{1}=\{2,4\}$ , $B_{2}=\{3,4\}$ and $A=$$(\begin{array}{llll}1 0 1 10 1 0 11 0 1 01 1 0 1\end{array})$$\phi_{3}(b_{0;}t_{1},t_{2})$

$=$

. Let

$X_{n}^{(i)}= \sum_{j=1}^{n}I_{B}.\cdot(Z_{j})(i=1,2)$. For $n=3$ , the p.g.f. is$\frac{1}{108}+\frac{73}{3564}t_{1}+\frac{73}{2376}t_{2}+\frac{269}{7920}t_{1^{2}}+\frac{3209}{35640}t_{1}t_{2}+\frac{269}{7920}t_{2^{2}}$$+ \frac{1}{20}t_{1^{3}}+\frac{3361}{23760}t_{1^{2}}t_{2}+\frac{3191}{35640}t_{1}t_{2^{2}}+\frac{1}{80}t_{2^{3}}+\frac{269}{1980}t_{1^{3}}t_{2}+\frac{4951}{35640}t_{1^{2}}t_{2^{2}}$$+ \frac{269}{11880}t_{1}t_{2^{3}}+\frac{73}{594}t_{1^{3}}t_{2^{2}}+\frac{73}{2376}t_{1^{2}}t_{2^{3}}+\frac{1}{27}t_{1^{3}}t_{2^{3}}$.

36
Table 1. The exact joint probability function of$(X_{3}^{(1)},X_{3}^{(2)})$, given $b_{0}=(1,2,1,2)$ .

$\overline{\frac{X_{3}^{(1)}--0X_{3}^{(1)}--1X_{3}^{(1)}--2X_{3}^{(1)}=3}{X_{3}^{(2)}=00.0092590.0204820.0339650.05-}-}$$X_{3}^{(2)}=1$$X_{3}^{(2)}=2$$X_{3}^{(2)}=3$

0.030724
0.033965

0.090039
0.089534

0.01250.022643 0.030724 0.037037

0.141456
0.138917

0.135859
0.122896

For $n=10$ , we give Fig.1, which is the three dimensional plot of the exact joint proba, given $b_{0}=(1,2,1,2)$ and the addition matrix .
bility function of$(X_{10}^{(1)}, X_{10}^{(2)})$$A$

Fig.1. The exact joint probability function of(1, 2, 1, 2) and the addition matrix A.

$(X_{10}^{(1)}, X_{10}^{(2)})$in the Example 4.1, given $b_{0}=$Marshall (1990) discussed this model in case that the addition matrix is the identity
matrix. So far as we know, it was first proposed by Kaiser and Stefansky (1972).
Example 4.2 :The Polya urn model containing 2different labels

Assume that $b0=(2,3)$ , $B=\{1,2\}$ , $B_{1}=\{2\}$ and $A=$$\sum_{\mathrm{j}=1}^{n}I_{B_{1}}(Zj)$$(\begin{array}{ll}1 01 1\end{array})$. Let$\mathrm{Y}_{n}=$. For $n=10$ , the p.g.f. and the expected value are, respectively,$\psi_{10}(b_{0;}t_{1})=\frac{1}{91}+\frac{125291}{3153150}t_{1}+\frac{4404557}{50450400}t_{1^{2}}+\frac{52734593}{367567200}t_{1^{3}}+\frac{8659858873}{46313467200}t_{1^{4}}$$+ \frac{985104707}{5028319296}t_{1^{5}}+\frac{195631373}{1197218880}t_{1^{6}}+\frac{8913571}{84651840}t_{1^{7}}+\frac{16000}{323323}t_{1^{8}}$$+ \frac{10240}{676039}t_{1}^{9}+\frac{1536}{676039}t_{1}^{10}$,$E[ \mathrm{Y}_{10;}b_{0}]=\dot{\psi}_{10}(b_{0;}1)=\frac{11750459755829}{2529873145800}=4.644683381$.

37
We give Fig.2, which is the two dimensional plot of the exact expected values ofgiven three initial urn compositions $b_{0}=(1,1)$ , $(2, 3)$ , $(5, 1)$ and the addition matrix$\mathrm{Y}_{n}$

$A$

,

.

$=$
The exact expected values of Yn, given three initial urn compositions$(1,1)$ , $(2, 3)$ , $(5, 1)$ and the addition matrix
in Example 4.2, Value , , III are, respectively,

Fig.2.

$b_{0}$$A$$\mathrm{I}$$\mathrm{I}\mathrm{I}$the values given initial urn compositions $b_{0}=(1,1)$ , $(2, 3)$ , $(5, 1)$ .

Remark 2In this example, Kotz, Mahmoud and Robert (2000) suggested that the fixedvalues of the initial condition ill be asymptotically negligible with rega$rd$ tofor large$narrow\infty$, as. By calculating the exact expected values of given
andthree initial conditions, we observe that their values depend on the initial conditions
when is small.
still
However, whencomes to 250, it seems that the exact expected values ofheavily depend on their initial conditions. Therefore, we think that the exact analysis is$\mathrm{Y}_{n}$$n$$E[\mathrm{Y}_{n}]\sim n/\ln n$$\mathrm{Y}_{n}$$n$$\mathrm{Y}_{n}$$n$important.

REFERENCES[1] Aki, S., Balakrishnan, N. and Mohanty, S. G. (1996), Sooner and later waiting time
problems and failure runs in higher order Markov dependent trials, Ann. Inst. Statist.
Math.,48,773-787.
[2] Aki, S. and Hirano, K. (1988), Some characteristics of the binomial distribution of orderk and related distributions, in Statistical Theory and Data Analysis II, Proceedings of
the Second Pacific Area Statistical Conference (Eds.K.Matusita), 211-222, Amsterdam:
North-Holland38[3] Aki, S. and Hirano, K. (1993), Discrete distributions related to succession events in a
tw0-state Markov chain, Statistical Sciences and Data Analysis; Proceedings of the Third
Pacific Area Statistical Conference (eds. K. Matusita, M. L. Puri and T. Hayakawa),
467-474, VSP International Science Publishers, Zeist.
[4] Aki, S. and Hirano, K. (1999), Sooner and later waiting time problems for runs in Markov
dependent bivariate trials, Ann. Inst. Statist. Math.,51,17-29.

[5] Bagchi, A. and Pal, A. (1985), Asymptotic normality in the generalized P\’olya-Eggenberger
urn model with application to computer data structures, SIAM J. Algebraic Discrete Methods, 6, 394-405.
[6] Ebneshahrashoob, M. and Sobel, M. (1990), Sooner and later waiting time problems for
Bernoulli trials: frequency and run quotas, Statist. Probab. Lett.,9,5-11.
[7] Feller, W. (1968), An Introduction to Probability Theorry and Its Applications, Vol. I, 3rded., Wiley, New York.
[8] Friedman, B. (1949), Asimple urn model, Cornrn. Pure Appl. Math.,2,59-70.
[9] Gouet, R. (1989), Amartingale approach to strong convergence in ageneralized P\’olyaEggenberger urn model, Statist. Probab. Lett.,9, 225-228.
[10] Gouet, R. (1993), Martingale functional central limit theorems for ageneralized Polya urn,
A nn. Pro bab.,21,1624-1639.
[11] Inoue, K. and Aki, S. (2000), Generalized waiting time problems associated with patterns
in P\’olya’s urn scheme, Research Report on Statistics, BO, Osaka University.
[12] Johnson, N. L. and Kotz, S. (1977), Urn Models and Their Applications, Wiley, New York.
[13] Johnson, N. L., Kotz, S. and Balakrishnan, N. (1997), Discrete Multivariate Distributions,Wiley, New York.
[14] Kaiser, H. F. and Stefansky, W. (1972), APolya distribution for teaching, Amer. Statist,
26, 40-43.
[15] Kocherlakota, S. (1989), Anote on the bivariate binomial distribution, Statist. Probab.
Lett.,9,21-24.
[16] Kotz, S., Mahmoud, H. and Robert, P. (2000), On generalized Polya urn models, Statist.
Probab. Lett., 9, 163-173.
[17] Mahmoud, H. and Smythe, R. T. (1991), On the distribution of leaves in rooted subtreesof recursive trees, Ann. Appl. Probab., 1, 406-418.
[18] Marshall, A. W. and Olkin, I. (1985), Afamily of bivariate distributions generated by thebivariate Bernoulli distribution, J. Amer. Statist. Assoc, 80, 332-338.
[19] Marshall, A. W. and Olkin, I. (1990), Bivariate distributions generated from P\’olyaEggenberger urn models, J. Multivariate Anal, 35, 48-65.
[20] Marshall, A. W. and Olkin, I. (1993), Bivariate life distributions from Polya’s urn model
for contagion, J. Appl. Prob., 30, 497-508.
[21] Smythe, R. (1996), Central limit theorems for urn models, Stochastic Process. Appl, 65,

115-137.