Unbalanced multi-drawing urn with random addition matrix

Rafik, Aguech; Olfa, Selmi

doi:10.1016/j.ajmsc.2018.12.004

In this paper, we consider a two color multi-drawing urn model. At each discrete time step, we draw uniformly at random a sample of $m$ balls $(m \geq 1)$ and note their color, they will be returned to the urn together with a random number of balls depending on the sample’s composition. The replacement rule is a 2 × 2 matrix depending on bounded discrete positive random variables. Using a stochastic approximation algorithm and martingales methods, we investigate the asymptotic behavior of the urn after many draws.

1. Introduction

The classical Pólya urn was introduced by Pólya and Eggenberger [7] describing contagious diseases. The first model is as follows: An urn contains balls of two colors at the start, white and blue. At each step, one picks a ball randomly and returns it to the urn with a ball of the same color. Afterwards, there were many generalizations and urn model become a simple tool to describe several models such finance, clinical trials (see [19,22]), biology (see [11]), computer sciences, internet (see [8,18]), etc...

Recently, Mahmoud, Chen, Wei, Kuba and Sulzbach [4,5,12–15], have focused on the multi-drawing urn. Instead of picking a ball,one picks a sample of $m$ balls (⁠ $m \geq ℓ$ ⁠), say $ℓ$ white and $(m - ℓ)$ blue balls. The pick is returned back to the urn together with $a_{m - ℓ}$ white and $b_{m - ℓ}$ blue balls, where $a_{ℓ}$ and $b_{ℓ}, 0 \leq ℓ \leq m$ are integers. At first, they treated two particular cases when { $a_{m - ℓ} = c \times ℓ and b_{m - ℓ} = c \times (m - ℓ)$ } and when { $a_{m - ℓ} = c \times (m - ℓ)$ and $b_{m - ℓ} = c \times ℓ$ }, where $c$ is a positive constant. By different methods as martingales and moment methods, the authors described the asymptotic behavior of the urn composition. When considering the general case and in order to ensure the existence of a martingale, they supposed that $W_{n}$ ⁠, the number of white balls in the urn after $n$ draws, satisfies the affinity condition i.e, there exist two deterministic sequences $(α_{n})$ and $(β_{n})$ such that, for all $n \geq 0$ ⁠, $E [W_{n + 1} | ℱ_{n}] = α_{n} W_{n} + β_{n}$ ⁠. Under this condition, the authors focused on small and large index urns. Later, the affinity condition was removed in the work of Lasmer, Mailler and Selmi [16], they generalized this model and looked at the case of more than two colors.

This paper contains the first results about multi drawing Pólya urns with random replacement rule. Even in the classical Pólya urn, where one ball is picked at every time step very few results cover the unbalanced case: exceptions are the works of Janson and Aguech. In [9] Janson studied a generalized urn model containing $q$ different colors (⁠ $q \geq 1$ ⁠) with a $q \times q$ replacement matrix $A$ with random entries such that $A_{i, j} \geq 0$ and $E (A_{i, j}^{2}) < \infty$ for all $i, j = 1, \dots, q$ ⁠. Janson considered the case when the mean of $A$ is an irreducible matrix. Using the method of embedding in continuous time of Athrea and Karlin [3], he gave explicit formulas for the asymptotic variances and covariances as well as functional limit theorems for the urn. Then, Janson [10] considered a particular two color Pólya urn model evolving according to a triangular replacement matrix (the matrix in non irreducible) with deterministic entries. He established theorems describing the asymptotic behavior of the composition of the urn after $n$ draws. Afterwards, Aguech [1] extended some results and studied two colors urn model with triangular replacement matrix. The entries of such a matrix, $X_{n}, Y_{n}$ and $C_{n}$ ⁠, are positive random variables with finite means and variances. The embedding in continuous times’ method were successful once again and he gave theorems about the asymptotic behavior of the urn’s composition after a long time.

In this paper, we deal with a two color unbalanced urn class with multiple drawing and random addition matrix. Consider $X$ and $Y$ two discrete-valued random variables. We assume that there exists two constants $U > 0$ and $L > 0$ such that $L \leq X \leq U$ and $L \leq Y \leq L$ ⁠. Let ${(X_{n})}_{n \geq 0}$ (resp ${(Y_{n \geq 0})}_{n \geq 0}$ ⁠) be a sequence of independent random variables distributed like $X$ (resp $Y$ ⁠). The sequences $X_{n}$ and $Y_{n}$ are not assumed to be independent.

The model we study is defined as follows: An urn contains initially $W_{0}$ white balls and $B_{0}$ blue balls, we fix an integer $m \geq 1$ ⁠, at a discrete step $n \geq 1$ ⁠, we draw uniformly at random a sample of $m$ balls, we denote by $ξ_{n}$ the number of white balls among those $m$ balls (we assume that the initial composition of the urn is more than $m$ to make the first draw possible). We return the drawn sample together with $Q_{n} {(ξ_{n}, m - ξ_{n})}^{t}$ balls, where $Q_{n}$ is a 2 × 2 matrix depending on the random variables $X_{n}$ and $Y_{n}$ ⁠. Let us denote by $W_{n}$ (resp $B_{n}$ ⁠) the number of white balls (resp blue balls), $T_{n}$ the total number of balls and by $Z_{n}$ the proportion of white balls in the urn at time $n$ ⁠. In other words, the process is defined recursively as follows: for all $n \geq 1$

(\begin{array}{l} W_{n} \\ B_{n} \end{array}) \underline{\underline{D}} (\begin{array}{l} W_{n - 1} \\ B_{n - 1} \end{array}) + Q_{n} (\begin{array}{c} ξ_{n} \\ m - ξ_{n} \end{array}) .

(1)

Let $ℱ_{n}$ be the $σ$ -field generated by the first $n$ draws. Note that, with these notations, we have for $k \in {0, \dots, m},$

ℙ [ξ_{n} = k | ℱ_{n - 1}] = \frac{(\underset{k}{W_{n - 1}}) (\underset{m - k}{B_{n - 1}})}{(\underset{m}{T_{n - 1}})} .

(2)

Thus, conditioning on $ℱ_{n - 1}$ the variable $ξ_{n}$ has an hypergeometric distribution with parameters $m, Z_{n - 1}$ and $T_{n - 1}$ ⁠. Some particular cases were the interest of recent works [4,15] and [2], where the authors characterized the urn models defined by Eq. (1) for the following cases

Q_{n} \in {(\begin{matrix} a & 0 \\ 0 & a \end{matrix}), (\begin{matrix} 0 & a \\ a & 0 \end{matrix}), (\begin{matrix} a & 0 \\ 0 & b \end{matrix}), (\begin{matrix} 0 & a \\ b & 0 \end{matrix})},

where $a, b$ are strictly positive integers. To generalize the previous works, we consider the urn models evolving according to Eq. (1) with

Q_{n} \in {(\begin{matrix} X_{n} & 0 \\ 0 & Y_{n} \end{matrix}), (\begin{matrix} 0 & X_{n} \\ Y_{n} & 0 \end{matrix}), (\begin{matrix} X_{n} & 0 \\ 0 & X_{n} \end{matrix}), (\begin{matrix} 0 & X_{n} \\ X_{n} & 0 \end{matrix})} .

The main idea is to use the stochastic algorithms and martingales in order to prove that the number of white balls in the urn converges almost surely and to study its fluctuations around its limit whenever it is possible.

The paper is organized as follows. In Section 2, we give the main results of the paper. Section 3 is devoted to the details of the stochastic approximation algorithm’s method. The proofs of the main results are detailed in Section 4.

2. Main results

We start with some notations. The notation $a . s .$ stands for almost surely. For a random variable $R$ ⁠, we denote by

μ_{R} = E (R) and σ_{R}^{2} = V a r (R),

by $μ_{X} : = μ_{X_{1}}$ (respectively $μ_{Y} : = μ_{Y_{1}}$ ⁠) and $σ_{X}^{2} : = σ_{X_{1}}^{2}$ (respectively $σ_{Y}^{2} : = σ_{Y_{1}}^{2}$ ⁠). For $x_{n}$ and $y_{n}$ two sequences of real numbers such that $y_{n} \neq 0$ for all $n$ ⁠, we denote $x_{n} = o (y_{n})$ (respectively $x_{n} = o (y_{n}), a . s$ ⁠) if $\lim_{n \to + \infty} x_{n} / y_{n} = 0$ (if $\lim_{n \to + \infty} x_{n} / y_{n} = 0, a . s$ when $x_{n}$ and $y_{n}$ are random).

In this section we state our main result. As mentioned in the introduction, we study urn models evolving according to Eq. (1). Recall that in the whole of paper we consider ${(X_{n})}_{n \geq 1}$ (resp ${(Y_{n})}_{n \geq 1}$ ⁠), a sequence of independent random variables distributed like $X$ (resp $Y$ ⁠).

The present theorem deals with an urn evolving with an anti-diagonal replacement matrix. The model is then opposite reinforced, i.e the more color is drawn the more it reinforces the opposite color.

Theorem 1.

Let $z : = \frac{\sqrt{μ_{X}}}{\sqrt{μ_{X}} + \sqrt{μ_{Y}}}$ and consider the urn model evolving by the matrix $Q_{n} = (\begin{array}{l} 0 & X_{n} \\ Y_{n} & 0 \end{array})$ ⁠. We have the following results:

(1) The total number of balls in the urn after n draws satisfies
$T_{n} = \sqrt{μ_{X} μ_{Y}} m n + o (n), a . s .$
(3)
and the number of white and blue balls in the urn after $n$ draws satisfy
$W_{n} = μ_{X} (1 - z) m n + o (n), a . s .$
$B_{n} = μ_{Y} z m n + o (n), a . s .$
(2) Furthermore, with $G (x) = \sum_{i = 0}^{4} a_{i} x^{i}$ ⁠, the normalized number of white balls in the urn satisfies the central limit theorem
$\frac{W_{n} - z T_{n}}{\sqrt{n}} \overset{D}{\to} N (0, \frac{G (z)}{3}), a s n \to + \infty .$
(4)
(3) Furthermore, when $Y_{n} = X_{n}$ for all $n \geq 0$ , the total number of balls in the urn after $n$ draws satisfies, for any $δ > \frac{1}{2}$
$T_{n} = m μ_{X} n + o (\sqrt{n} \ln^{δ} n), a . s .$
The number of white balls $W_{n}$ and blue balls $B_{n}$ in the urn after $n$ draws satisfy for any $δ > \frac{1}{2},$
$W_{n} = \frac{m μ_{X}}{2} n + o (\sqrt{n} \ln^{δ} n), a . s,$
$B_{n} = \frac{m μ_{X}}{2} n + o (\sqrt{n} \ln^{δ} n), a . s .$
We have the convergence in distribution:
$lim_{n \to + \infty} \frac{W_{n} - \frac{1}{2} T_{n}}{Σ \sqrt{n}} = N (0, 1) and lim_{n \to + \infty} \frac{W_{n} - E (W_{n})}{Σ_{1} \sqrt{n}} = N (0, 1);$
where
$Σ = \frac{m}{12} (σ_{X}^{2} + μ_{X^{2}}) and Σ_{1} = \frac{m}{12} [(σ_{X}^{2} + μ_{X^{2}}) + m^{2} σ_{X}^{2}] .$

Example 1.

Let $X_{n} = a$ and $Y_{n} = b$ (where $a$ and $b$ are not random), then $z = \frac{\sqrt{a}}{\sqrt{a} + \sqrt{b}}$ ⁠. This case was studied in [2] and the authors proved the following

\sqrt{n} (\frac{W_{n}}{T_{n}} - z) \overset{D}{\to} N (0, \frac{\sqrt{a b}}{3 m {(\sqrt{a} + \sqrt{b})}^{2}}), as n \to \infty .

Under the notation of Theorem 1, we easily compute $G (z) = m a b z (1 - z)$ and then the particular case is proved again.

Example 2.

Let $X_{n} = Y_{n} = C$ (non random), the urn is balanced and the total number of balls is deterministic and satisfies $T_{n} = T_{0} + C m n$ ⁠. Furthermore, we have $μ_{X} = C$ and $σ_{X}^{2} = 0$ ⁠, applying Theorem 1 $(3)$ we obtain the following limit:

\frac{W_{n} - \frac{C m n}{2}}{\sqrt{n}} \overset{D}{\to} N (0, \frac{m C^{2}}{12}), as n \to \infty .

Kuba et al. [15] studied this particular case and established such a result via two different methods: The recursion formulas permit to derive the expression of the higher moments of the number of white balls and then to conclude functional limit theorem. The same result was proved via martingales method.

In the following theorem, we consider a diagonal replacement matrix $Q_{n}$ ⁠. The model is self reinforced since the rich gets richer. As the particular case when $m = 1$ ⁠, we compare $\frac{μ_{X}}{μ_{Y}}$ with 1, we will distinguish different phases.

Theorem 2.

Consider the urn evolving by the matrix $Q_{n} = (\begin{array}{l} X_{n} & 0 \\ 0 & Y_{n} \end{array}) .$

(1) If $μ_{X} > μ_{Y}$ ⁠, then the total number of balls in the urn after $n$ draws satisfies
$T_{n} = m μ_{X} n + o (n), a . s .,$
and the asymptotic composition of the urn is
$W_{n} = m μ_{X} n + o (n), B_{n} = B_{\infty} n^{ρ} + o (n^{ρ}), a . s .$
where $ρ = \frac{μ_{Y}}{μ_{X}}$ and $B_{\infty}$ is a positive random variable.
(2) If $μ_{X} = μ_{Y}$ , the composition of the urn after $n$ draws satisfies
$T_{n} = m μ_{X} n + o (n), a . s .$
In addition, there exists a positive random variable $W_{\infty}$ such that,
$W_{n} = W_{\infty} n + o (n) and B_{n} = (μ_{x} m - W_{\infty}) n + o (n), a . s .$
(3) Furthermore, if for all $n \geq 0$ , $Y_{n} = X_{n}$ ⁠, the distribution of the random variable $W_{\infty}$ is absolutely continuous.

Remark.

The case when $μ_{X} < μ_{Y}$ is obtained by interchanging the colors. In fact we have the following almost sure results:

T_{n} = m μ_{Y} n + o (n), W_{n} = W_{\infty} n^{σ} + o (n) and B_{n} = m μ_{Y} n + o (n),

where $W_{\infty}$ is a positive random variable and $σ = \frac{μ_{X}}{μ_{Y}} .$

Example 3.

Aguech [1] studied the particular case when $m = 1$ and considered the following triangular replacement matrix

(\begin{array}{l} X_{n} & 0 \\ C_{n} & Y_{n} \end{array}),

where $X_{n}, Y_{n}$ and $C_{n}$ are independent positive random variables with finite means and variances. Via embedding in continuous time method and martingales, the author proved, for $C_{n} = 0$ ⁠, the following almost sure results:

(a) If $μ_{X} > μ_{Y}$ ⁠,
$W_{n} = μ_{X} n + o (n), B_{n} = D n^{ρ} and T_{n} = μ_{X} n + o (n),$
where $ρ = \frac{μ_{Y}}{μ_{X}}$ and $D$ is a positive random variable.
(b) If $μ_{X} = μ_{Y}$ ⁠,
$W_{n} = μ_{X} \frac{W}{W + B} n + o (n) and B_{n} = μ_{X} \frac{B}{W + B} n + o (n),$
where $W$ and $B$ are the almost sure limit of a continuous time martingale.

We prove again these results in Theorem 2 using stochastic approximation algorithm.

Example 4.

Chen and Kuba [4] studied the case when $X_{n} = Y_{n} = C$ (⁠ $C$ is non random) and $m \geq 1$ ⁠. They gave explicit expressions of moment of all order of $W_{n} / n$ and proved that its almost sure limit, $W_{\infty}$ cannot be an ordinary $B e t a$ distribution, unlike the original Pòlya urn model [7] when $X = C$ and $m = 1$ ⁠, Eggenberger and Pólya proved in 1923 that the random variable $W_{\infty} / C$ has a Beta distribution with parameters $(B_{0} / C, W_{0} / C)$ ⁠. Unfortunately, in our model we cannot yet derive the expression of higher moments of $W_{n} / n$ since the recurrence formulas are too intricate.

3. Some results on stochastic approximation algorithm

The stochastic algorithm approximation plays a crucial role in the proofs in order to describe the asymptotic composition of the urn. As many versions of the stochastic algorithm exist in the literature (see [6] for example), we adapt the version of Renlund in [20,21].

Definition 1.

A stochastic approximation algorithm ${(U_{n})}_{n \geq 0}$ is a stochastic process taking values in $[0,1]$ and adapted to a filtration $F_{n}$ that satisfies

U_{n + 1} - U_{n} = γ_{n + 1} (f (U_{n}) + Δ M_{n + 1}),

(5)

where ${(γ_{n})}_{n \geq 1}$ and ${(Δ M_{n})}_{n \geq 1}$ are two $F_{n}$ -measurable sequences of random variables, $f$ is a function from $[0, 1]$ into $ℝ$ such that $f (0) \geq 0$ ⁠, $f (1) \leq 0$ and the following conditions hold almost surely: There exists constants $c_{1}, c_{2}, K_{Δ},$ and $K_{f}$ positive real numbers such that for any $n \geq 1$ ⁠,

(i) $\frac{c_{1}}{n} \leq γ_{n} \leq \frac{c_{2}}{n}$ ;
(ii) $E ((Δ M_{n + 1})^{2} | ℱ_{n}) \leq K_{Δ}$ ⁠;
(iii) $| f (U_{n}) | \leq K_{f}$ ⁠;
(iv) $E [γ_{n + 1} Δ M_{n + 1} | ℱ_{n}] = 0$ ⁠.

Definition 2.

Let $Z_{f} = {x \in [0, 1]; f (x) = 0} .$ ⁠. A zero $p \in Z_{f}$ will be called stable if there exists a neighborhood $N_{p}$ of $p$ such that $f (x) (x - p) < 0$ whenever $x \in N_{p} ∖ {p} .$ If $f$ is differentiable, then $f' (p)$ is sufficient to determine that $p$ is stable.

Remark.

Note that Assumption $(i i)$ in Definition 1 is not stated as in [20] where it is assumed that there exists a positive constant $K_{Δ}$ such that $| Δ M_{n} | \leq K_{Δ}$ ⁠.

We have the following result about the process defined by Eq. (5)

Proposition 1.

Let ${(U_{n})}_{n \geq 0}$ be a stochastic algorithm defined by Eq. (5). If $f$ is continuous, then $\lim_{n \to + \infty} U_{n}$ exists almost surely and is a stable zero of $f$ .

The following lemmas will be useful for the proof of Proposition 1.

Lemma 1.

Define $V_{n} = \sum_{i = 1}^{n} γ_{i} Δ M_{i}$ . Under the assumptions of Proposition 1, $V_{n}$ converges almost surely.

Proof. Under the assumptions mentioned in Definition 1, we have

E (V_{n + 1} | F_{n}) = V_{n} + E (γ_{n + 1} Δ M_{n + 1} | F_{n}) = V_{n} .

We deduce that ${(V_{n}, ℱ_{n})}_{n}$ is a martingale. On the other hand,

E (V_{n}^{2}) = \sum_{i = 1}^{n} E (γ_{i}^{2} {(Δ M_{i})}^{2}) \leq \sum_{i = 1}^{n} \frac{c_{2}^{2}}{i^{2}} E ({(Δ M_{i})}^{2}) \leq K_{Δ} c_{2}^{2} \sum_{i = 1}^{n} \frac{1}{i^{2}} < \infty .

It follows that ${(V_{n})}_{n}$ is an $L^{2}$ - bounded martingale, and thus, it converges almost surely. □

Next lemma ensures that, under the assumptions of Proposition 1, all possible candidates for the almost sure limit of $U_{n}$ are necessary among the zeros of $f$ ⁠.

Lemma 2 ([20]).

Let $Z_{f} = {x; f (x) = 0}$ be the set of zeros of $f$ and let $C (U_{n})$ be the set of limit points of ${U_{n}}$ defined by

C (U_{n}) = ⋂_{n \geq 1} \bar{{U_{n}, U_{n + 1}, \dots}},

where $\bar{A}$ denotes the closure of a set $A$ ⁠. Under the assumptions ofProposition 1, if $f$ is continuous, then,

ℙ (C (U_{n}) \subseteq Z_{f}) = 1.

Lemma 3 ([20]).

Suppose that $f (x) < - δ$ (or $f (x) > δ$ ) for some $δ > 0$ , whenever $x \in (a_{0}, b_{0})$ . Then,

C (U_{n}) ⋂ (a_{0}, b_{0}) = Ø a . s .,

and either

\lim \sup_{n} U_{n} \leq a_{0}

or

\lim \inf_{n} U_{n} \geq b_{0} .

We are now able to handle the proof of Proposition 1.

Proof of Proposition 1.

The proof is close to Theorem 1 in [20], for the convenience of the reader, we resume the proof and we mention the main steps. If $\lim_{n \to + \infty} U_{n}$ does not exist, we can find two rational numbers in the open interval

$] {\lim \inf}_{n \to + \infty} U_{n}, {\lim \sup}_{n \to + \infty} U_{n} [$ ⁠. Let $\lim \inf U_{n} < p < q < \lim \sup U_{n}$ be two arbitrary different rational numbers. If we can show that

ℙ ({\lim \inf U_{n} \leq p} \cap {\lim \sup U_{n} \geq q}) = 0,

then, the existence of the limit will be established and the claim of the proposition follows from Lemma 2. For this reason, we need to distinguish two different cases whether or not

p

and

q

are in the same connected component of

Z_{f}

⁠.

Case 1: $p$ and $q$ are not in the same connected component of $Z_{f}$ ⁠: Since $Z_{f}$ is closed and $f$ is continuous there must exist $[a, b] \subseteq [p, q] ⋂ Z_{f}^{c}$ such that $f$ is non-zero and has a constant sign for all $x \in (a, b)$ ⁠. By Lemma 3, it is impossible to have $\lim \inf_{n} U_{n} \leq a$ and $\lim \sup_{n} U_{n} \geq b$ ⁠.

Case 2: $p$ and $q$ are in the same connected component of $Z_{f}$ ⁠: In all the cases of our framework $Z_{f}$ is a set of two isolated points, therefore we are not interested to the case when $p$ and $q$ are not in the same connected component.

To establish that the almost sure limit of $U_{n}$ is among the stable point set, we refer the reader to [20] to see a detailed proof. □

Next result is due to Renlund [21] which will be used in the proofs of Theorems 1 and 2.

Theorem 3 ([21]).

Let ${(U_{n})}_{n \geq 0}$ satisfy Eq. (5) and that $\lim_{n \to + \infty} U_{n} = U^{*}$ . Let

{\hat{γ}}_{n} : = n γ_{n} \hat{f} (U_{n - 1}), where \hat{f} (x) = \frac{f (x)}{U^{*} - x} .

If ${\hat{γ}}_{n}$ converges almost surely to some limit $\hat{γ} > \frac{1}{2}$ and if $E [{(n γ_{n} Δ M_{n})}^{2} | ℱ_{n - 1}] \to σ^{2} > 0,$ then, we have the convergence in distribution

\sqrt{n} (U_{n} - U^{*}) \overset{D}{\to} N (0, \frac{σ^{2}}{2 \hat{γ} - 1}) .

4. Proof of the main results

4.1 Prerequisite for the proofs of the main results

We show in the following that the stochastic approximation algorithm is a fruitful method to study unbalanced urn models. Although there are few versions of such a method that permit to $γ_{n}$ to be random, the version of Renlund [20] and [21] applies to our model.

Under the assumptions of Theorem 1 and according to Eq. (1), the compositions of the urn satisfy the following recursions:

W_{n + 1} = W_{n} + X_{n + 1} (m - ξ_{n + 1})

(6)

and

T_{n + 1} = T_{n} + m X_{n + 1} + ξ_{n + 1} (Y_{n + 1} - X_{n + 1}) .

(7)

We start with first results that will be useful for the proof of Theorem 2.

Lemma 4 (Technical Lemma).

For all integers $m, A, B$ such that $m \leq A + B$ we have

\sum_{m = 0}^{m} k (\begin{array}{l} A \\ k \end{array}) (\begin{array}{l} B \\ m - k \end{array}) = A (\begin{array}{l} A + B - 1 \\ m - 1 \end{array})

and

\sum_{m = 0}^{m} k^{2} (\begin{array}{l} A \\ k \end{array}) (\begin{array}{l} B \\ m - k \end{array}) = A (A - 1) (\begin{array}{c} A + B - 2 \\ m - 2 \end{array}) + A (\begin{array}{c} A + B - 1 \\ m - 1 \end{array})

Remark.

Since conditioning on $ℱ_{n - 1}$ the variable $(ξ_{n})$ has an hypergeometric distribution with parameters $m$ ⁠, $Z_{n - 1}$ and $T_{n - 1}$ ⁠, it follows from Lemma 4 the following:

E (ξ_{n} | ℱ_{n - 1}) = m Z_{n},

and

V a r (ξ_{n} | ℱ_{n - 1}) = m Z_{n - 1} (1 - Z_{n - 1}) \frac{T_{n - 1} - m}{T_{n - 1} - 1} .

Lemma 5.

Under the assumptions of Theorem 1, the proportion of white balls after $n$ draws, $Z_{n}$ , satisfies the stochastic algorithm defined by (5), where $γ_{n} = \frac{1}{T_{n}}$ ,

f (x) = m (μ_{X} - μ_{Y}) x^{2} - 2 μ_{X} m x + μ_{X} m,

and

Δ M_{n + 1} = D_{n + 1} - E [D_{n + 1} | ℱ_{n}],

with

D_{n + 1} = ξ_{n + 1} (Z_{n} (X_{n + 1} - Y_{n + 1}) - X_{n + 1}) + m X_{n + 1} (1 - Z_{n}) .

Proof. In view of the recursions in Equations (6), (7) we have

\begin{array}{l} Z_{n + 1} - Z_{n} = \frac{1}{T_{n + 1}} [W_{n} + X_{n + 1} (m - ξ_{n + 1}) - Z_{n} (T_{n} + m X_{n + 1} + ξ_{n + 1} (Y_{n + 1} - X_{n + 1}))] \\ = \frac{1}{T_{n + 1}} [X_{n + 1} (m - ξ_{n + 1}) - Z_{n} (m X_{n + 1} + ξ_{n + 1} (Y_{n + 1} - X_{n + 1}))] \\ = \frac{D_{n + 1}}{T_{n + 1}} . \end{array}

An easy computation shows that $E (D_{n + 1} | ℱ_{n}) = m (μ_{X} - μ_{Y}) Z_{n}^{2} - 2 m μ_{X} Z_{n} + m μ_{X}$ ⁠. □

Using Proposition 1, we show that the almost sure limit of the proportion of white balls in the urn depends on the means of the variables $X_{n}$ and $Y_{n}$ ⁠:

Proposition 2.

The proportion of white balls in the urn after $n$ draws, under the assumptions of Theorem 1, satisfies

\lim_{n \to + \infty} Z_{n} = z : = \frac{\sqrt{μ_{X}}}{\sqrt{μ_{X}} + \sqrt{μ_{Y}}}, a . s .

(8)

Proof. In view of Lemma 5, we check the assumptions of Definition 1, indeed,

(i)
an easy computation shows that
$T_{n} = T_{0} + m \sum_{i = 1}^{n} (m - ξ_{i}) X_{i} + \sum_{i = 1}^{n} ξ_{i} Y_{i} .$
(9)
Since for all $n \geq 1$ we have $0 \leq ξ_{n} \leq m$ ⁠, $L \leq X_{n} \leq U$ and $L \leq Y_{n} \leq U$ ⁠, then
$m n L \leq T_{n} \leq T_{0} + m n U .$
Then the following bound holds, for all $n \geq 1$
$\frac{c_{1}}{n} \leq \frac{1}{T_{n}} \leq \frac{c_{2}}{n},$
(10)
with $c_{1} = \frac{1}{T_{0} + m U}$ and $c_{2} = \frac{1}{m L} .$
(ii)
$E [{(Δ M_{n + 1})}^{2} | ℱ_{n}] \leq (μ_{{(X - Y)}^{2}} + 3 μ_{X}) (m + m^{2}) + 5 m^{2} μ_{X^{2}} + 2 m^{2} μ_{X} μ_{Y} + m^{2} (| μ_{X} - μ_{Y} | + 3 μ_{X}) = K_{Δ},$
(iii)
$| f (Z_{n}) | \leq m (| μ_{Y} - μ_{X} | + 3 μ_{X}) = K_{f},$
(iv)
$E [\frac{1}{T_{n + 1}} Δ M_{n + 1} | ℱ_{n}] \leq \frac{1}{T_{n}} E [Δ M_{n + 1} | ℱ_{n}] = 0.$

Since the function $f$ ⁠, defined in Lemma 5, is continuous, we conclude by Proposition 1, that the process $Z_{n}$ converges $a . s .$ to

z = \frac{\sqrt{μ_{X}}}{\sqrt{μ_{X}} + \sqrt{μ_{Y}}},

which is the unique zero of $f$ with negative derivative. □

The following Lemma will intervene in the proof of Theorem.

Lemma 6.

Under the assumptions of Theorem 1, the total number of balls after $n$ draws satisfies

\lim_{n \to + \infty} \frac{T_{n}}{n} = m \sqrt{μ_{X} μ_{Y}}, a . s .

Proof. Let $G_{n} = \sum_{i = 1}^{n} [ξ_{i} (Y_{i} - X_{i}) - E [ξ_{i} (Y_{i} - X_{i}) | ℱ_{i - 1}]],$ by the recursive Eq. (7), we have

\frac{T_{n}}{n} = \frac{T_{0}}{n} + \frac{m}{n} \sum_{i = 1}^{n} X_{i} + \frac{m (μ_{Y} - μ_{X})}{n} \sum_{i = 1}^{n} Z_{i - 1} + \frac{G_{n}}{n} .

Since ${(X_{i})}_{i \geq 1}$ are i.i.d. random variables, then by the strong law of large numbers we have

\frac{m}{n} \sum_{i = 1}^{n} X_{i} \overset{a . s}{\to} m μ_{X} .

Via Proposition 2 and Cesáro lemma, we conclude that $\frac{1}{n} \sum_{i = 1}^{n} Z_{i - 1}$ converges $a . s .$ ⁠, as $n$ goes to infinity, to $z$ ⁠. Finally, we prove that the last term in the right side tends $a . s .$ to zero, as $n$ tends to infinity. In fact, $(G_{n}, ℱ_{n})$ is a martingale difference sequence with quadratic variation given by

{〈 G 〉}_{n} = \sum_{i = 1}^{n} E [{(\nabla G_{i})}^{2} | ℱ_{i - 1}],

where $\nabla G_{n} = G_{n} - G_{n - 1} = ξ_{n} (Y_{n} - X_{n}) - E [ξ_{n} (Y_{n} - X_{n}) | ℱ_{n - 1}]$ ⁠. By a simple computation, we have the almost sure convergence

\lim_{n \to + \infty} E [{(\nabla G_{n})}^{2} | ℱ_{n - 1}] = (m z (1 - z) + m^{2} z^{2}) (σ_{Y}^{2} + σ_{X}^{2}) .

Therefore, Cesáro lemma ensures that $a . s .$

\lim_{n \to + \infty} \frac{{〈 G 〉}_{n}}{n} = (m z (1 - z) + m^{2} z^{2}) (σ_{Y}^{2} + σ_{X}^{2}) .

It follows that $\frac{G_{n}}{n} \overset{a . s}{\to} 0$ ⁠. Thus, for $n$ large enough, we have

\frac{T_{n}}{n} \overset{a . s}{\to} m \sqrt{μ_{X} μ_{Y}} . □

(11)

Remark.

The convergence in Proposition 2 holds also in $L^{2}$ ⁠.

Under the hypothesis of Theorem 2, the process of the urn satisfies the following recursions:

W_{n + 1} = W_{n} + X_{n + 1} ξ_{n + 1} and T_{n + 1} = T_{n} + m Y_{n + 1} + ξ_{n + 1} (X_{n + 1} - Y_{n + 1}) .

(12)

Next results will be used in the proof of Theorem 2.

Lemma 7.

Under the assumptions of Theorem 2, if $μ_{X} \neq μ_{Y}$ , the proportion of white balls in the urn after $n$ draws satisfies the stochastic algorithm defined by Eq. (5) where $γ_{n} = 1 / T_{n}$ ,

f (x) = m (μ_{Y} - μ_{X}) x (x - 1),

and

Δ M_{n + 1} = D_{n + 1} - E [D_{n + 1} | ℱ_{n}],

with

D_{n + 1} = ξ_{n + 1} (Z_{n} (Y_{n + 1} - X_{n + 1}) + X_{n + 1}) - m Z_{n} Y_{n + 1} .

Proof. We check that, if $μ_{X} \neq μ_{Y}$ ⁠, the assumptions of Definition 1 hold. Indeed,

(i)
Eq. (12) shows that
$T_{n} = T_{0} + m \sum_{i = 1}^{n} Y_{i} + \sum_{i = 1}^{n} ξ_{i} (X_{i} - Y_{i}),$
(13)
since the expression of $T_{n}$ is similar to that in Equation (9), we have the same bound of $γ_{n} = \frac{1}{T_{n}}$ defined in Eq. (10).
(ii)
$E [{(Δ M_{n + 1})}^{2} | ℱ_{n}] \leq (2 m + m^{2}) (4 μ_{X^{2}} + μ_{Y^{2}}) + 3 m^{2} μ_{Y^{2}} + 2 m^{2} μ_{X} + 2 m^{2} μ_{X} μ_{Y} + 4 m^{2} {(μ_{X} - μ_{Y})}^{2} = K_{Δ} .$
(iii)
$| f (Z_{n}) | = | m (μ_{Y} - μ_{X}) Z_{n} (Z_{n} - 1) | \leq 2 m | μ_{Y} - μ_{X} | = K_{f},$
(iv)
$E [γ_{n + 1} Δ M_{n + 1} | ℱ_{n}] \leq \frac{1}{T_{n}} E [Δ M_{n + 1} | ℱ_{n}] = 0.$ □

Proposition 3.

Under the assumptions of Theorem 2, the proportion of white balls in the urn after $n$ draws, $Z_{n}$ , satisfies $a . s .$

\lim_{n \to + \infty} Z_{n} = {\begin{array}{l} 0, & if μ_{X} < μ_{Y}; \\ 1, & if μ_{X} > μ_{Y}; \\ {\tilde{Z}}_{\infty}, & if μ_{X} = μ_{Y}, \end{array}

where

{\tilde{Z}}_{\infty}

is a positive random variable.

Proof. Recall that, if $μ_{X} \neq μ_{Y}$ ⁠, $Z_{n}$ satisfies the stochastic algorithm of Lemma 7. As the function $f$ is continuous, by Theorem 3 we conclude that $Z_{n}$ converges $a . s .$ to the stable zero of the function $h$ with a negative derivative, which is $1$ if $μ_{X} > μ_{Y}$ and $0$ if $μ_{X} < μ_{Y} .$

In the case when $μ_{X} = μ_{Y}$ ⁠, we have $Z_{n + 1} = Z_{n} + \frac{P_{n + 1}}{T_{n + 1}}$ ⁠, where

P_{n + 1} = X_{n + 1} ξ_{n + 1} - Z_{n} (m Y_{n + 1} + ξ_{n + 1} (X_{n + 1} - Y_{n + 1})) .

Since $E [P_{n + 1} | ℱ_{n}] = 0$ ⁠, then $Z_{n}$ is a positive martingale which converges $a . s .$ to a positive random variable ${\tilde{Z}}_{\infty}$ ⁠. □

As a consequence of Proposition 3, we have

Corollary 1.

Suppose that $μ_{X} \geq μ_{Y}$ , the total number of balls in the urn, $T_{n}$ , satisfies as $n$ tends to infinity

\lim_{n \to + \infty} \frac{T_{n}}{n} = m μ_{X}, a . s .

Remark.

The convergence in Corollary 1 holds also in $L^{2}$ ⁠.

Proof.

We have

\frac{T_{n}}{n} = \frac{T_{0}}{n} + \frac{m}{n} \sum_{i = 1}^{n} Y_{i} + \frac{1}{n} \sum_{i = 1}^{n} ξ_{i} (X_{i} - Y_{i}) = \frac{T_{0}}{n} + \frac{m}{n} \sum_{i = 1}^{n} Y_{i} + \frac{m (μ_{X} - μ_{Y})}{n} \sum_{i = 1}^{n} Z_{i - 1} - \frac{G_{n}}{n},

where

G_{n} = \sum_{i = 1}^{n} [ξ_{i} (Y_{i} - X_{i}) −E (ξ_{i} (Y_{i} - X_{i}) | ℱ_{n})]

is the martingale difference defined in the proof of Lemma 6. Recall that

G_{n} / n

converges

a . s .

to

0

and that

Z_{n}

converges

a . s .

to

1

when

μ_{X} > μ_{Y}

⁠, . Then, using Cesáro lemma, we obtain the limits requested. If

μ_{X} = μ_{Y}

⁠, we have

\frac{1}{n} \sum_{i = 1}^{n} Y_{i}

converges to

μ_{X}

⁠. □

For the particular case when $X_{n} = Y_{n}$ for all $n$ ⁠, we have the following results

Proposition 4 ([5]).

Let ${(Ω_{l})}_{l \geq 0}$ be a sequence of increasing events such that $ℙ (\cup_{l \geq 0} Ω_{l}) = 1$ . If there exists nonnegative Borel measurable function ${f_{l}}_{l \geq 1}$ such that for all Borel sets B

ℙ (Ω_{l} \cap W_{\infty}^{- 1} (B)) = \int_{B} f_{l} (x) d x

then, $f = \lim_{l \to + \infty} f_{l}$ exists almost everywhere and $f$ is the density of $W_{\infty}$ .

Lemma 8.

Define the events

Ω_{l} : = {W_{l} \geq m U and B_{l} \geq m U},

then, ${(Ω_{l})}_{l \geq 0}$ is a sequence of increasing events, moreover we have $ℙ (\cup_{l \geq 0} Ω_{l}) = 1$ .

Let ${(p_{c})}_{c \in supp (X)}$ the distribution of $X$ ⁠.

Lemma 9.

For a fixed $l > 0$ , there exists a positive constant $κ$ , such that, for every $c \in supp (X)$ , $n \geq l + 1$ , $U m \leq j \leq T_{l - 1}$ and $k \leq U m (n + 1)$ , we have

\sum_{i = 0}^{m} ℙ (W_{n + 1} = j + k | W_{n} = j + k - c i) \leq p_{c} (1 - \frac{1}{n} + \frac{κ}{n^{2}}) .

(14)

Proof. According to Lemma 4.1 in [5], for $U m \leq j \leq T_{l - 1}$ ⁠, $n \geq l$ and $k \leq U m (n + 1)$ ⁠, the following holds:

\sum_{i = 0}^{m} (\begin{array}{c} j + c (k - i) \\ i \end{array}) (\begin{array}{c} T_{n} - j - c (k - i) \\ m - i \end{array}) = \frac{T_{n}^{m}}{m!} + \frac{(1 - m - 2 c) T_{n}^{m - 1}}{2 (m - 1)!} + \dots,

(15)

which is a polynomial in $T_{n}$ of degree $m$ with coefficients depending on $W_{0}, B_{0}, m$ and $c$ only.

Let $u_{n, k} (c) = \sum_{i = 0}^{m} ℙ (W_{n + 1} = j + k | W_{n} = j + k - i c)$ ⁠. Applying Eq. (15) to our model we have almost surely

\begin{array}{l} u_{n, k} (c) = p_{c} \sum_{i = 0}^{m} (\begin{array}{c} j + k \\ i \end{array}) (\begin{array}{c} T_{n} - j - k \\ m - i \end{array}) {(\begin{array}{c} T_{n} \\ m \end{array})}^{- 1} \\ = p_{c} {(\begin{array}{c} T_{n} \\ m \end{array})}^{- 1} (\frac{T_{n}^{m}}{m!} + \frac{(1 - m - 2 c)}{(m - 1)!} T_{n}^{m - 1} + \dots) \times {(\frac{T_{n}^{m}}{m!} + \frac{(1 - m)}{2 (m - 1)!} T_{n}^{m - 1} + \dots)}^{- 1} \\ = p_{c} (1 - \frac{1}{n} + O (\frac{1}{n^{2}})) . □ \end{array}

4.2 Proof of Theorem 1

Recall that ${(X_{i})}_{i \geq 1}$ (resp ${(Y_{i})}_{i \geq 1}$ ⁠) is a sequence of random variable distributed like $X$ (resp $Y$ ⁠). We consider the urn model evolving by the anti-diagonal matrix $Q_{n} = (\begin{array}{l} 0 & X_{n} \\ Y_{n} & 0 \end{array})$ ⁠.

Proof of claim 1

Theorem 1. In order to describe the asymptotic of the urn’s composition we use Lemma 6 which gives the estimate of $T_{n}$ ⁠, the total number of balls in the urn after $n$ draws. For the number of white and blue balls we have, $a . s .$

\frac{W_{n}}{n} = \frac{W_{n}}{T_{n}} \frac{T_{n}}{n} and \frac{B_{n}}{n} = \frac{B_{n}}{T_{n}} \frac{T_{n}}{n},

using Eqs. (8), (11) and Slutsky theorem, we have almost surely, as $n$ goes to infinity,

\frac{W_{n}}{n} \to m \sqrt{μ_{X} μ_{Y}} z and \frac{B_{n}}{n} \to m \sqrt{μ_{X} μ_{Y}} (1 - z) .

These convergence hold also in $L^{2}$ ⁠.

Proof of claim 2

Theorem 1. To establish a central limit theorem, we aim to apply Theorem 3. Recall that in our model, we have $γ_{n} = 1 / T_{n}$ ⁠, then we need to find the following limits:

\lim_{n \to + \infty} E [{(\frac{n}{T_{n}})}^{2} Δ M_{n + 1}^{2} | ℱ_{n}] and \lim_{n \to + \infty} \frac{n}{T_{n}} f^{'} (Z_{n}) .

In fact, in view of Lemma 6, we have $n / T_{n}$ converges $a . s .$ to ${(m \sqrt{μ_{X} μ_{Y}})}^{- 1}$ and

E [{(Δ M_{n + 1})}^{2} | ℱ_{n}] = E [{(D_{n + 1})}^{2} | ℱ_{n}] + E {[D_{n + 1} | ℱ_{n}]}^{2} .

Since $E {[D_{n + 1} | ℱ_{n}]}^{2}$ converges $a . s .$ to ${(f (z))}^{2} = 0$ ⁠, we have,

E ({(Δ M_{n + 1})}^{2} | ℱ_{n}] = E [Z_{n}^{2} {(X_{n + 1} - Y_{n + 1})}^{2} - 2 Z_{n} X_{n + 1} + X_{n + 1} | ℱ_{n}] E [ξ_{n + 1}^{2} | ℱ_{n}] + m^{2} E (X^{2}) + 2 m^{2} (Z_{n}^{2} (E (X^{2}) - μ_{X} μ_{Y}) - Z_{n} E (X^{2})) .

Using the fact that

E [ξ_{n + 1}^{2} | ℱ_{n}] = m Z_{n} (1 - Z_{n}) \frac{T_{n} - m}{T_{n} - 1} + m^{2} Z_{n}^{2}

and that $Z_{n}$ converges $a . s .$ to $z$ ⁠, we conclude that $E [D_{n + 1}^{2} | ℱ_{n}]$ converges $a . s .$ to $G (z) > 0.$ Applying Theorem 3, we obtain the following

\sqrt{n} (Z_{n} - z) \overset{L}{\to} N (0, \frac{G (z)}{3 m^{2} μ_{X} μ_{Y}}) .

Since we have

\frac{W_{n} - z T_{n}}{\sqrt{n}} = \sqrt{n} (\frac{W_{n}}{T_{n}} - z) \frac{T_{n}}{n},

Slutsky theorem is enough to conclude the proof.

Proof of claim 3

Theorem 1. In this particular case, the claims (1) and (2) apply and the almost sure limit of the urn’s composition follows immediately as well as a central limit theorem. Furthermore, as such a case is easier, we can obtain a finer rate of convergence of the normalized number of balls in the urn. We also give another version of central limit theorem satisfied by $W_{n}$ using the weak dependence between the variables ${(ξ_{i})}_{i \geq 0}$ and the Bernstein’s method.

Recall that when $Y_{n} = X_{n}$ for all $n \geq 0$ ⁠, the urn is evolving according to Eq. (1) with a replacement matrix given by

Q_{n} = (\begin{array}{l} 0 & X_{n} \\ X_{n} & 0 \end{array}) .

Theorem 1 $(1)$ applies for $z = 1 / 2$ and the following almost sure results follows:

T_{n} = m μ_{X} n + o (n), W_{n} = \frac{m μ_{X}}{2} n + o (n) and B_{n} = \frac{m μ_{X}}{2} n + o (n) .

On the other hand, the total number of balls in the urn is a sum of i.i.d. random variables $T_{n} = T_{0} + \sum_{i = 1}^{n} X_{i}$ ⁠. According to the strong law of large number we get a finer rate of convergence of $T_{n}$ ⁠, we have for $δ > \frac{1}{2}$

T_{n} = m μ_{X} n + o (\sqrt{n} \ln^{δ} n) .

(16)

Using $\frac{W_{n}}{n} = \frac{W_{n}}{T_{n}} \frac{T_{n}}{n}$ and Eq. (16), we have

\frac{W_{n}}{n} \overset{a.s}{=} (\frac{1}{2} + o (1)) (μ_{X} m + o (\frac{\ln^{δ} n}{\sqrt{n}})) .

We conclude that the number of white balls in the urn after $n$ draws, $W_{n}$ ⁠, satisfies almost surely for $n$ large enough

W_{n} = \frac{μ_{X} m}{2} n + o (\sqrt{n} \ln^{δ} n), δ > \frac{1}{2} .

Remark.

In such a model, the proportion of white balls in the urn, $Z_{n}$ ⁠, satisfies the stochastic approximation algorithm defined by Eq. (5) with $γ_{n} = 1 / T_{n}$ ⁠,

f (x) = μ_{X} m (1 - 2 x)

and

Δ M_{n + 1} = X_{n + 1} (m - ξ_{n + 1} - m Z_{n}) - μ_{X} m (1 - 2 Z_{n}) .

Moreover, we propose the following result about the variance of $W_{n}$ ⁠.

Proposition 5.

Under the hypothesis of Theorem 1, with $Y_{n} = X_{n}$ for all $n \geq 0$ , the variance of $W_{n}$ satisfies for every $δ > \frac{1}{2},$

V ar (W_{n}) = \frac{m (σ_{X}^{2} + μ_{X}^{2}) + m^{2} σ_{X}^{2}}{12} n + o (\sqrt{n} \ln^{δ} n) .

(17)

Proof. Because the number of white balls in the urn satisfies Eq. (6), we write

V ar (W_{n + 1}) = V ar (W_{n}) + V ar (X_{n + 1} (m - ξ_{n + 1})) + 2 ℂ ov (W_{n}, X_{n + 1} (m - ξ_{n + 1})) .

We have

V ar (X_{n} (m - ξ_{n})) = E (X^{2}) V ar (m - ξ_{n + 1}) + V ar (X) E ({(m - ξ_{n + 1})}^{2}) = (σ_{X}^{2} + μ_{X}^{2}) [E (V ar (ξ_{n + 1} | ℱ_{n})) + V ar (E (ξ_{n + 1} | ℱ_{n}))] + σ_{x}^{2} E ({(m - ξ_{n + 1})}^{2}) = (σ_{x}^{2} + μ_{X^{2}}) (V ar (m Z_{n}) + E (m Z_{n} (1 - Z_{n}) \frac{T_{n} - m}{T_{n} - 1})) + σ_{X}^{2} E {(m - ξ_{n})}^{2} .

(18)

On the other hand, since the variables ${(X_{i})}_{i \geq 0}$ are independent then $X_{n + 1}$ and $W_{n}$ are independent, thus it follows

\begin{array}{l} ℂ o v (W_{n}, X_{n + 1} (m - ξ_{n + 1})) = ℂ o v (W_{n}, m X_{n + 1}) - ℂ o v (W_{n}, X_{n + 1} ξ_{n + 1}) \\ = - ℂ o v (W_{n}, X_{n + 1} ξ_{n + 1}) \\ = - m μ_{X} [E (W_{n} \frac{W_{n}}{T_{n}}) + E (W_{n}) E (\frac{W_{n}}{T_{n}})] \\ = - m μ_{X} (\frac{1}{m μ_{X}} (1 + o (\frac{\ln^{δ} n}{\sqrt{n}})) V ar (W_{n})) \end{array}

(19)

Using Eqs. (18) and (19) and the fact that $Z_{n} \overset{a.s}{\to} \frac{1}{2}$ as $n$ goes to infinity, we obtain

V ar (W_{n + 1}) = (1 - \frac{2}{n} + o (\frac{\ln^{δ} n}{n^{\frac{3}{2}}})) V ar (W_{n}) + \frac{m (σ_{X}^{2} + μ_{X^{2}}) + m^{2} σ_{X}^{2}}{4} + o (\frac{\ln^{δ} n}{\sqrt{n}}) = a_{n} V ar (W_{n}) + b_{n},

where $a_{n} = (1 - \frac{2}{n} + o (\frac{\ln^{δ} n}{n^{\frac{3}{2}}}))$ and $b_{n} = \frac{m (σ_{X}^{2} + μ_{X^{2}}) + m^{2} σ_{X}^{2}}{4} + o (\frac{\ln^{δ} n}{\sqrt{n}}) .$

Thus,

V ar (W_{n}) = (\prod_{k = 1}^{n} a_{k}) (V ar (W_{0}) + \sum_{k = 0}^{n - 1} \frac{b_{k}}{\prod_{j = 0}^{k} a_{j}}) .

There exists a constant $a$ such that $\prod_{k = 1}^{n} a_{k} = \frac{e^{a}}{n^{2}} (1 + o (\frac{\ln^{δ} n}{\sqrt{n}}))$ ⁠, which leads to

V ar (W_{n}) = \frac{m (σ_{X}^{2} + μ_{X^{2}}) + m^{2} σ_{X}^{2}}{12} n + o (\sqrt{n} \ln^{δ} n), δ > \frac{1}{2} . □

In this particular case, two versions of the central limit theorem for the number of white balls are proved. The first version is deduced by Theorem 1(2) and the second one is proved using the weak dependence between the variables ${(ξ_{i})}_{i \geq 1}$ together with Bernstein’s Method.

Applying Theorem 1(2), we have $Y_{n} = X_{n}$ ⁠, it follows that $μ_{Y} = μ_{X}$ ⁠, by a simple computation for the coefficients $a_{i}$ for $i \in {0, \dots, 4}$ we have for $z = \frac{1}{2}$ :

G (\frac{1}{2}) = \frac{m}{4} (σ_{X}^{2} + μ_{X^{2}}) .

We conclude that, in distribution we have

\frac{W_{n} - \frac{1}{2} T_{n}}{\sqrt{n}} \to N (0, \frac{m}{12} (σ_{X}^{2} + μ_{X^{2}})) .

A second central limit theorem is satisfied by $W_{n}$ ⁠. As the proof is close to that of Lemma 3 and Theorem 4 in [2], we will mention only the main steps and we refer the reader to [2] for the details. The idea of the proof is the following: Once we prove that the variables ${(X_{n} (m - ξ_{n}))}_{n \geq 0}$ are $α$ -mixing variables with a strong mixing coefficient $α (n) = o (\ln^{δ} n / \sqrt{n})$ ⁠, $δ > 1 / 2$ (see Lemma 3 in [2] for detailed computations), Bernstein’s method (see [17]) will be suitable. Consider the same notations as in Theorem 4 in [2] with

{\tilde{ξ}}_{i} = X_{i} (m - ξ_{i}) - μ_{X} (m - E (ξ_{i})), S_{n} = \frac{1}{\sqrt{n}} \sum_{i = 1}^{n} {\tilde{ξ}}_{i}

and $N$ is the centered normal random variable with variance

σ^{2} = \frac{m}{12} [(σ_{X}^{2} + μ_{X^{2}}) + m^{2} σ_{X}^{2}] .

Actually, all that remains in this case, is to compute the variance of $W_{n}$ ⁠. For that, we use Proposition 5. As a conclusion,

\frac{W_{n} - E (W_{n})}{\sqrt{n}} \overset{D}{\to} N (0, \frac{m}{12} (σ_{X}^{2} + μ_{X^{2}}) + m^{2} σ_{X}^{2}) .

4.3 Proof of Theorem 2

Theorem 2 deals with unbalanced urn model with diagonal replacement matrix. We applied Proposition 1 to find the almost sure limit of the proportion of white balls in the urn. The stochastic algorithm applies only to the case when $μ_{X} \neq μ_{Y}$ ⁠, because when $μ_{X} = μ_{Y}$ we fall on the case $f \equiv 0$ ⁠. Furthermore, Theorem 3 does not work, in fact, by a simple computation we obtain $σ = 0$ ⁠. Such a result is expected since that even for the case $X_{n} = Y_{n} = C$ (⁠ $C$ is constant) and $m > 1$ ⁠, the fluctuations of $W_{n} / n$ around its limit has not a normal distribution.

Consider the urn model defined by Eq. (1) with $Q_{n} = (\begin{array}{l} X_{n} & 0 \\ 0 & Y_{n} \end{array})$ ⁠.

Proof of claims 1 and 2

Theorem 2. Corollary 1 ensures that, if $μ_{X} \geq μ_{Y}$ we have

T_{n} = m μ_{X} n + o (n) .

Indeed,

If $μ_{X} > μ_{Y}$ ⁠, we have, a.s.,

\lim_{n \to + \infty} \frac{W_{n}}{n} = \lim_{n \to + \infty} \frac{W_{n}}{T_{n}} \frac{T_{n}}{n} = m μ_{X} .

Moreover, let ${\tilde{G}}_{n} = {(\prod_{i = 1}^{n - 1} (1 + \frac{m μ_{Y}}{T_{i}}))}^{- 1} B_{n},$ then $({\tilde{G}}_{n}, ℱ_{n})$ is a positive martingale. There exists a positive number $A$ such that $\prod_{i = 1}^{n - 1} (1 + \frac{m μ_{Y}}{T_{i}}) ≃ A n^{ρ}$ where $ρ = \frac{μ_{Y}}{μ_{X}}$ ⁠. Then, as $n$ tends to infinity we have

\frac{B_{n}}{n^{ρ}} \overset{a . s}{\to} B_{\infty},

where $B_{\infty}$ is a positive random variable.

• If $μ_{X} = μ_{Y}$ ⁠, the sequences ${(\prod_{i = 1}^{n - 1} (1 + \frac{m μ_{X}}{T_{i}}))}^{- 1} W_{n}$ and ${(\prod_{i = 1}^{n - 1} (1 + \frac{m μ_{Y}}{T_{i}}))}^{- 1} B_{n}$ are $ℱ_{n}$ -martingales such that ${(\prod_{i = 1}^{n - 1} (1 + \frac{m μ_{X}}{T_{i}}))}^{- 1} ≃ B n,$ where $B > 0$ ⁠, then, as $n$ tends to infinity, we have

\frac{W_{n}}{n} \to W_{\infty} and \frac{B_{n}}{n} \to {\tilde{B}}_{\infty}, a . s .,

where $W_{\infty}$ and ${\tilde{B}}_{\infty}$ are positive random variables satisfying ${\tilde{B}}_{\infty} = m μ_{X} - W_{\infty} .$

Proof of claim 3

Theorem 2. We consider the case when $Y_{n} = X_{n}$ for all $n \geq 0$ ⁠, The urn model is then evolving according to the recursive Eq. (1) with the replacement matrix

Q_{n} = (\begin{array}{l} X_{n} & 0 \\ 0 & X_{n} \end{array}) .

Since Theorem 2 $(2)$ applies to that case, we obtain the following strong law of large number

\frac{W_{n}}{n} \overset{a . s}{\to} W_{\infty} and \frac{B_{n}}{n} \overset{a . s}{\to} (μ_{X} m - W_{\infty}),

where $W_{\infty}$ is a positive random variable. Furthermore, as $T_{n}$ is a sum of i.i.d. random variables then $T_{n}$ satisfies for every $δ > \frac{1}{2}$

T_{n} \overset{a . s}{=} \frac{μ_{X} m}{2} n + o (\sqrt{n} \ln^{δ} n), a . s .

(20)

To prove that $W_{\infty}$ is absolutely continuous, we follow the proof of Theorem 4.2 in [5] and we give the main steps. The idea is the following: given the sequence of increasing event $Ω_{l}$ defined in Lemma 8, if we show that the restriction of $W_{\infty}$ on every $Ω_{l, j} = {ω; W_{l} (ω) = j}$ has a density for each $j$ ⁠, with $U m \leq j \leq T_{l - 1}$ ⁠, then Proposition 4 ensures the existence of the density of $W_{\infty}$ almost every where. In fact, for a fixed $l$ and $n \geq l + 1$ ⁠, we denote by $v_{n, j} = \max_{0 \leq k \leq U m n} ℙ (W_{l + n} = j + k | W_{l} = j)$ ⁠. We have the following inequality:

\begin{array}{l} v_{n + 1, j} \leq \max_{0 \leq k \leq U m (n + 1)} {\sum_{i = 0}^{m} \sum_{c \in \sup p (X)} ℙ (W_{l + n + 1} = j + k | W_{l + n} = j + k - c i)} \\ \leq \max_{0 \leq k \leq U m (n + 1)} {\sum_{i = 0}^{m} \sum_{c \in supp (X)} ℙ (W_{l + n + 1} = j + k | W_{l + n} = j + k - c i) \times ℙ (W_{l + n} = j + k - c i | W_{l} = j)} \\ \leq \max_{0 \leq k \leq U m (n + 1)} \sum_{i = 0}^{m} \sum_{c \in supp (X)} ℙ (W_{l + n + 1} = j + k | W_{l + n} = j + k - c i) \\ \times \max_{0 \leq \tilde{k} \leq U m n} ℙ (W_{l + n} = j + \tilde{k} | W_{l} = j) \leq \sum_{c \in supp (X)} p_{c} (1 - \frac{1}{n + l} + \frac{κ}{{(n + l)}^{2}}) v_{n, j} \\ = (1 - \frac{1}{n + l} + \frac{κ}{{(n + l)}^{2}}) v_{n, j} . \end{array}

This implies that there exists some positive constant $C (l)$ ⁠, depending on $l$ only, such that, for a fixed $l$ and for all $n \geq l + 1$ ⁠, we get

\max_{0 \leq k \leq m (n - l)} ℙ (W_{n} = j + k | W_{l} = j) \leq \prod_{i = l}^{n} (1 - \frac{1}{i} + \frac{κ}{i^{2}}) \leq \frac{C (l)}{n} .

(21)

Let $ε > 0$ and $δ = \frac{ε}{C (l)}$ ⁠, and setting $x_{1} < x_{1}^{'} \leq x_{2} < x_{2}^{'} \leq \dots \leq x_{r} < x_{r}^{'}$ such that $\sum_{i = 1}^{r} | x_{i}^{'} - x_{i} | \leq δ .$ By Fatou’s lemma we have

\begin{array}{l} \sum_{i = 1}^{r} ℙ ({x_{i} \leq W_{\infty} \leq x^{'}} \cap Ω_{l, j}) \leq \sum_{i = 1}^{r} \lim \inf ℙ (x_{i} \leq \frac{W_{n}}{n} \leq x_{i}^{'} | W_{l} = j) ℙ (Ω_{l, j}) \\ \leq \sum_{i = 1}^{r} \lim \inf (((x_{i}^{'} - x_{i}) n + 1) \frac{C (l)}{n}) \\ \leq \sum_{i = 1}^{r} (x_{i}^{'} - x_{i}) C (l) = ε . \end{array}

Then the proof follows.

Outlook: We suggest that if we replace the boundedness hypothesis of the variables $X$ and $Y$ by the assumption that $X$ and $Y$ have finite moments of order $2$ , our results remain true.

The first author is grateful to the King Saud University, Deanship of Scientific Research, College of Science Research Center. The authors also thank two anonymous referees for their valuable comments and suggestions. The publisher wishes to inform readers that the article “Unbalanced multi-drawing urn with random addition matrix” was originally published by the previous publisher of the Arab Journal of Mathematical Sciences and the pagination of this article has been subsequently changed. There has been no change to the content of the article. This change was necessary for the journal to transition from the previous publisher to the new one. The publisher sincerely apologises for any inconvenience caused. To access and cite this article, please use Rafik, A., Olfa, S. (2019), “Unbalanced multi-drawing urn with random addition matrix” Arab Journal of Mathematical Sciences, Vol. 26 No. 1/2, pp. 57-74. The original publication date for this paper was 11/01/2019.

References

[1]

R.

Aguech

,

Limit theorems for random triangular urns schemes

,

J. Appl. Probab.

46

(

3

) (

2009

)

827

–

843

.

Google Scholar

Crossref

[2]

R.

Aguech

, et al.,

A generalized urn model with multiple drawing and random addition

,

Ann. Inst. Statist. Math.

(

2018

)

1

–

20

.

Google Scholar

[3]

K.B.

Athrea

,

S.

Karlin

,

Embedding of urns schemes into continuous time Markov branching processes and related limit theorems

,

Ann. Math. Stat.

39

(

1968

)

1801

–

1817

.

Google Scholar

Crossref

[4]

M.R.

Chen

,

M.

Kuba

,

On generalized polya urn models

,

J. Appl. Probab.

50

(

4

) (

2013

)

909

–

1216

.

Google Scholar

[5]

M.R.

Chen

,

C.Z.

Wei

,

A new urn model

,

J. Appl. Probab.

42

(

4

) (

2005

)

964

–

976

.

Google Scholar

Crossref

[6]

M.

Duflo

,

Random Iterative Models

,

Springer-Verlag

,

Berlin

,

1997

.

Google Scholar

[7]

F.

Eggenberger

,

G.

Pólya

,

Über die statistik verkeletter vorgange

,

Z. Angew. Math. Mech.

3

(

1923

)

279

–

289

.

Google Scholar

Crossref

[8]

R.N.

Goldman

,

Polya’s urn model and computer aided geometric design

,

SIAM J. Algebr. Discrete Methods

6

(

1

) (

1985

)

1

–

28

.

Google Scholar

Crossref

[9]

S.

Janson

,

Functionnal limt theorems for multitype branching processes and generalized pólya urns

,

Stochastic Process. Appl

.

110

(

2

) (

2004

)

177

–

245

.

Google Scholar

Crossref

[10]

S.

Janson

,

Limit theorems for triangular urn schemes

,

Probab. Theory Related Fields

134

(

3

) (

2006

)

417

–

452

.

Google Scholar

Crossref

[11]

N.L.

Johnson

,

S.

Kotz

,

Urn Models and Their Application

,

John Wiley & Sons

,

1977

.

Google Scholar

[12]

M.

Kuba

,

H.

Mahmoud

,

Two-colour balanced affine urn models with multiple drawings II: large-index and triangular urns

,

2016

,

arXiv:150909053

.

Google Scholar

[13]

M.

Kuba

,

H.

Mahmoud

,

Two-colour balanced affine urn models with multiple drawings I: Central limit theorem

,

Adv. Appl. Probab.

90

(

2017

)

1

–

26

.

Google Scholar

[14]

M.

Kuba

,

H.

Sulzbach

,

On martingale tail sums in affine two-color urn models with multiple drawings

,

J. Appl. Probab.

54

(

2017

)

1

–

21

.

Google Scholar

Crossref

[15]

M.

Kuba

, et al.,

Analysis of a generalized Friedman’s urn with multiple drawings

,

Discrete Appl. Math.

161

(

18

) (

2013

)

2968

–

2984

.

Google Scholar

Crossref

[16]

N.

Lasmar

, et al.,

Multiple drawing multi-colour urns by stochastic approximation

,

J. Appl. Probab.

55

(

1

) (

2018

)

254

–

281

.

Google Scholar

Crossref

[17]

Z.

Lin

,

C.

Lu

,

Limit Theory for Mixing Dependent Random Variables

,

Kluwer Academic Publishers

,

Boston

,

1996

.

Google Scholar

[18]

H.

Mahmoud

,

Random spouts as internet model and pólya processes

,

Acta inform

.

41

(

1

) (

2004

)

1

–

18

.

Google Scholar

Crossref

[19]

G.

Pagés

,

S.

Laruelle

,

Randomized urns models revisited using stochastic approximation

,

Ann. Appl. Probab.

23

(

4

) (

2013

)

1409

–

1436

.

Google Scholar

[20]

H.

Renlund

,

Generalized polya urns via stochastic approximation

,

2010

,

arxiv:10023716v1

.

Google Scholar

[21]

H.

Renlund

,

Limit theorem for Stochastic approximation algorithm

,

2011

,

arxiv:11024741v1

.

Google Scholar

[22]

L.J.

Wei

,

An application of an urn model to the design of sequential controlled clinical trials

,

J. Am. Stat. Assoc.

73

(

1978

)

559

–

563

.

Google Scholar

Crossref

2019

Aguech Rafik and Selmi Olfa

Published in the Arab Journal of Mathematical Sciences. Published by Emerald Publishing Limited. This article is published under the Creative Commons Attribution (CC BY 4.0) license. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this license may be seen at http://creativecommons.org/licences/by/4.0/legalcode

Unbalanced multi-drawing urn with random addition matrix

1. Introduction

2. Main results

3. Some results on stochastic approximation algorithm

4. Proof of the main results

4.1 Prerequisite for the proofs of the main results

4.2 Proof of Theorem 1

4.3 Proof of Theorem 2

References

Email Alerts

Cited By

Unbalanced multi-drawing urn with random addition matrix Open Access

1. Introduction

2. Main results

3. Some results on stochastic approximation algorithm

4. Proof of the main results

4.1 Prerequisite for the proofs of the main results

4.2 Proof of Theorem 1

4.3 Proof of Theorem 2

References

Email Alerts

Suggested Reading

Recommended for you

Cited By

Sharing Unavailable

Unbalanced multi-drawing urn with random addition matrix