1. Introduction
Urn models have been among the most popular probabilistic schemes and have received a lot of attention in the literature (see [1,2]). Let us describe the Pólya urn scheme briefly. In 1923, [3] proposed the following urn scheme to model processes such as the spread of infectious diseases. In this scheme, a single urn contains white balls and black balls. One ball is drawn at random and then replaced, together with balls of the same color. The procedure is repeated n times. It is known that the sequence of the proportions of white balls is a martingale converging almost surely to a random variable having a beta distribution with parameters and. Since then, numerous generalizations and extentions of the Pólya urn have been studied : see [4-14]. In 1990, [6] generalized the Pólya urn model with the single change that the number of extra balls added in the urn is a function of time. One ball is drawn and is replaced in the urn along with F(n) balls of the same color. In his setup can be any function. He showed that the proportions of white balls converge almost surely and the limit has no atom except possibly at 0 or 1.
In this paper, we propose a new class of discrete time stochastic processes generated by a two-color generalized Pólya urn that is reinforced every time. This is a generalization of the urn model considered in [10]. A single urn contains white balls and black balls: at discrete times we draw balls and note their colors, say are black and are white. We return the drawn balls to the urn. Moreover, new white balls and new black balls are added in the urn. The numbers and are random variables in. We show that the proportions of white balls form a bounded martingale sequence which converges almost surely. Necessary and sufficient conditions for the limit to have no atoms at 0 or 1 are given.
This paper is organized as follows. In Section 2, we set the probabilistic model for a randomly reinforced urn. In Section 3, we show that the proportions of white balls form a bounded martingale sequence which converges almost surely. Necessary and sufficient conditions for the limit to concentrate on the set are given. We conclude the paper by proving that interacting reinforced urn process are asymptotically exchangeable.
2. Model Description and Notation
On a rich enough probability space, define two sequences and of positive, integervalued random variables and let and are fixed positive integers. A randomly reinforced urn generates the stochastic processes. The sequences and respectively denote the number of black balls and white balls in the urn at time. The dynamics of the processes and are governed by the following: set and let
be a random variable. Now we iterate this sampling scheme forever. Thus, at time, given the sigma-field generated by, we consider that is a Hypergeometric random variable and we assume that and are independent conditionaly on. Finally, we set
(2.1)
This is a generalization of the reinforced urn model considered in [10]. Assume that, at each time periode a new firm appears on the market and have to choose operative systems among the systems A and B, for its computers. The firm can choose blocks of size of computers having the operative system. This choice depends on the number of computers having the operative system A on the market. The process given in (2.1) is going to describe the evolution along time of the proportion of computers operating systems A.
3. Martingale Property
The process is of primary interest for studying the stochastic processes generated by this generalization of Pólya’s urn. Here represents the proportion of white balls in the urn at time. We show that these proportions form a bounded martingale. This martingale converges almost surely. The next theorem is of fundamental importance, this is our main result.
Theorem 3.1. The sequence is a bounded martingale with respect to the filtration taking values in Therefore, it converges almost surely to a random variable
Proof.
Here with being the total number of balls in the urn at time. Now let us show that is a martingale. In fact
This shows that is -bounded martingale with respect to the filtration. Hence, there exists a random variable such that on a set of probability one.
The exact distribution of is unknown except in a few particular cases. The situation where almost surely for all and almost surely for all n corresponds to the classical Pólya-Eggenberger contagious urn scheme. In this case has a beta distribution with parameters and. Let us continue with the general case.
Theorem 3.2. The limit is Bernoulli distributed if and only if
Proof. From (2.1) we have
thus we get
The transition between the second equality and the third equality relies on the fact that, conditionally on are independent. As a result
, (3.1)
with
Now we set, and we have from (3.1)
Consequently, converges to if and only if Vn converges to, which happens whenever
. This is the desired result because a random variable satisfies the condition
if and only if is concentrated on the set.
This theorem applies, for example, when and almost surely. In fact from (3.1), we remark that when and almost surely (and be any function) we have
and we deduce
Consequently, converges to if and only if converges to, which happens whenever the product values
converges to
. This happens whenever
diverges.
Moreover, if and then
the general term of the series being proportional to.
From Theorem 3.1 we deduce thatCorollary 3.3. Assume that the sequence satisfies the following conditions
then
and
Proof. For every fixed and for sufficiently large,
Then, using the well know convergence of the hypergeometric probabilities to the binomial, we have
and the conclusion follows from the bounded convergence theorem.
As a consequence of Theorem (3.2), we have the following.
Corollary 3.4. Assume that the sequences and are bounded then
Proof. Since the sequences and are bounded by some constant and for all we obtain from (3.1) that
Let be such that. We obtain that
Now, since, then
and
so
The final result in this section shows that the law of large numbers holds for interacting reinforced urn systems.
Theorem 3.5. We have
with
Proof. Using Cesàro’s summability result we obtain that,
Let. Since then we have the following1), for all.
2) For all we have
This shows that the sequence is orthogonal, with zero mean.
3) For, we have
Therefore, the sequence satisfies the conditions of Hall’s theorem (see [15], Theorem 2.8, p. 22), and we can conclude that the series
(3.2)
Finally, Kronecker’s lemma yields
(3.3)
This shows that
(3.4)
which is the announced result.
4. Asymptotic Exchangeability
According to [16] a sequence of random variables is asymptotically exchangeable if the joint distribution of the sequence converges as to the distribution of some exchangeable sequence. In particular, we have the following lemma due to [17].
Lemma 6. (Aldous)
Consider be an infinite exchangeable sequence directed by.
1) Let be a regular conditional distribution for given.
Then
(4.1)
2) Let be an infinite sequence. Let be a regular conditinal distribution for given, and suppose that
Then
(4.2)
Theorem 3.1 together with Lemma yield that the sequence of random variables is asymptotically exchangeable. The main result of this section is the following.
Theorem 4.1. Under the conditions of Corollary 3.3, the sequence of random variables is asymptotically exchangeable.
Proof. For all, the conditional distribution of given, is such that
Hence, as in Corollary 3.3, we obtain that
The conclusion comes from Lemma 4.1, part (b).
5. Conclusions
Urn model have been widely studied and applied in both scientific and social science disciplines. In this paper, we have proposed a general class of discrete stochastic processes generated by a two-color generalized Pólya urn. This model generalizes a model previously studied by [10]. This paper also shows that the proportion of white balls form a bounded martingale sequence which converge almost surely. Asymptotic properties and asymptotic exchangeability are given. However, the complete characterization of the limit still remains to be resolved in the future and it would be interesting to explore the possibility extensions to more than two colors.
Another important application of this urn models is to randomize treatments to patients in a clinical trial (see [18]). Consider an urn containing balls of two type, representing two treatements. Patients normally arrive sequentially, and treatment assigned on the urn composition and previous treatment outcomes. For more details analysis on this application, we refer to [13].
6. Acknowledgements
The authors want to thank Professor Éric Marchand for his numerous advices and helpful discussions. The second author wants to thank NSERC for the financial support.
NOTES