Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-22T15:35:55.321Z Has data issue: false hasContentIssue false

Nonlinear and unbalanced urn models with two types of strategies: a stochastic approximation point of view

Published online by Cambridge University Press:  20 May 2022

Soumaya Idriss*
Affiliation:
University of Monastir, Monastir, Tunisia. E-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

In this paper, we treat a nonlinear and unbalanced $2$-color urn scheme, subjected to two different nonlinear drawing rules, depending on the color withdrawn. We prove a central limit theorem as well as a law of large numbers for the urn composition. We also give an estimate of the mean and variance of both types of balls.

Type
Research Article
Copyright
© The Author(s), 2022. Published by Cambridge University Press

1. Introduction

1.1. Overview

Urn models have been around for more than a century. The concept of urn models concerns an urn containing items, generally referred to as “balls,” and two main rules: a drawing rule, according to which the drawing of balls occurs, and a replacement rule. Given that the balls in an urn are of $d\geq 2$ different colors, the replacement rule is a $d\times d$ matrix. So basically, the procedure consists in drawing a sample of balls of size $m\geq 1$, checking their colors, then put them back into the urn along with new balls following what the replacement matrix dictates, i.e., say one draws $m_j$ balls of color $j$ with $m=\sum _{j=1}^{d}m_j$, the sample is placed back in the urn together with $R^{ij}m_i$ balls of type $i\in \{1,\ldots,d\}$ where $[R^{ij}]_{1\leq i,j\leq d}:=R$ is the replacement matrix.

One of the earliest works in the literature is that of Pólya and Eggenberger [Reference Eggenberger and Pólya9] in $1923$, as they introduced a $2$-color urn with a diagonal replacement matrix. In their model, one adds to the urn $a$ (a positive integer) balls of the same color as the ball withdrawn, according to a self-reinforcement scheme. Friedman [Reference Friedman10] extends the model in [Reference Eggenberger and Pólya9] to a model where one adds $a$ balls of the same color, and $b$ balls of the other color, using hence, a symmetric replacement matrix. Later on, came the work of Bagchi and Pal [Reference Bagchi and Pal3] where they broke the symmetry of Friedman's schemata to be adding $a$ balls of color $1$ and $b$ balls of color $2$ for a drawn ball of color $1$, $c$ balls of color $1$ and $d$ balls of color $2$ for a drawn ball of color $2$. Since then, several generalizations of these models have taken place and an essential survey of this issue can be found in the book of Mahmoud [Reference Mahmoud20]. While all of the previously-mentioned urn models dealt with different replacement rules, they all agreed on one drawing rule which is none other than the classic uniform probability rule given by:

$$\mathbb{P}(\textbf{X}_{n+1}=\textbf{e}_i\,|\,\mathscr{F}_{n})= \frac{Y^i_n}{T_n},\quad i \in\{1,\ldots,d\},$$

where the event $\{\textbf {X}_{n+1}=\textbf {e}_i\}$ represents the drawing of one $(m=1)$ ball from the urn and this ball is of color $i$, $Y^i_n$ denotes the number of balls of color $i$ in the urn at time $n$ and $(\mathscr {F}_n)_{n\geq 0}$ is the $\sigma$-algebra generated by the first $n$ draws. An urn obeying such linear drawing rule is called a single-drawing urn. Recently, Sophie Laruelle and Gille Pagès [Reference Laruelle and Pagès18] studied a $d$-color urn model in which the drawing rule is no longer linear but nonlinear, that is the drawn ball is of color $i\in \{1,\ldots, d\}$ with probability

$$\frac{f(Y^i_n)}{\sum^d_{j=1}f(Y_n^j)},\quad n\geq0,$$

where $f:\mathbb {R}_+\longrightarrow \mathbb {R}_+$ satisfying

$$f \ \text{is non-decreasing, convex or concave},\ f(0)=0,\ f(1)=1\ \text{and} \ \{f\gt0\}=(0,1].$$

The function $f$ being the skewing function, $f\neq id_{\mathbb {R}_+}$ as if $f(x)=x$, the model falls back onto a classic single $d$-color urn. The aim was to model the risk variation as the convexity stands for risk seeking and the concavity stands for the risk aversion. One of the latest additions to the urn models’ library, is the work of González-Navarrete and Lambert where they used the Bagchi-Pal urn scheme [Reference Bagchi and Pal3] and subjected it to two different strategies involving two players. The reader can refer to [Reference González-Navarrete and Lambert11] for more details.

Up to a recent time, the study of urn models relied heavily on the balance condition. An urn is called balanced if the number of new balls to add remains the same at each epoch of time. For example in the Bagchi-Pal urn scheme, one has $a+b=c+d=K$, $K$ is called the balance constant, which makes the urn composition deterministic at each step that is:

$$T_n=T_0+Kn, \quad n\geq0,$$

where $T_n$ denotes the total number of balls at the urn at stage $n$ and $T_0$ its initial composition. We should mention on one hand, that the balance condition is usually applied to the replacement matrix, but there exist in the literature some works in which the urn is balanced is mean (see [Reference Janson13,Reference Laruelle and Pagès17,Reference Laruelle and Pagès18,Reference Smythe25]), where the authors consider a randomized addition matrices $(D_n)_{n\geq 0}$ that are not balanced, whereas the generating matrices given by

$$H_n:=[\mathbb{E}(D^{ij}_{n}\,| \,\mathscr{F}_{n-1})]_{1\leq i,j\leq d},$$

are balanced. On the other hand, several recent papers provide models where the balance condition is dropped. For instance, Aguech et al. [Reference Aguech and Selmi1,Reference Aguech, Lasmar and Selmi2] study both self and opposite reinforcement schemata in an urn obeying a multiple drawing ($m\geq 1$) policy using both diagonal and anti-diagonal, unbalanced replacement matrix. That is, for $a$ and $b$ two strictly positive integers such that $a\neq b$, the replacement matrices are given by:

$$\underset{\text{self-reinforcement}}{R=\begin{pmatrix} a & 0 \\ 0 & b \end{pmatrix}}\quad \text{and}\quad \underset{\text{opposite-reinforcement}}{R=\begin{pmatrix} 0 & a \\ b & 0 \end{pmatrix}}.$$

In [Reference Idriss12], Idriss studies a $2$-dimensional version of that of [Reference Laruelle and Pagès18]. The model in [Reference Idriss12] treats a $2$-color nonlinear urn with unbalanced deterministic replacement matrix:

$$R=\begin{pmatrix} R^{11} & R^{12} \\ R^{21} & R^{22} \end{pmatrix} \quad \text{where} \ R^{11}+R^{21}\neq R^{12}+R^{22}.$$

The variety of balanced urn schemata gave birth to numerous techniques of study in order to establish limit theorems describing the asymptotic behavior of the urn composition, namely a strong law of large numbers (an SLLN) and a central limit theorem (a CLT), and to give estimates for the moments of the number of balls of each type. To learn about these techniques, the reader may refer to ([Reference Bai and Hu4Reference Eggenberger and Pólya9,Reference González-Navarrete and Lambert11,Reference Janson13Reference Kuba and Mahmoud16,Reference Lasmar, Mailler and Selmi19]). In the unbalanced case, the authors resorted to a technique called Stochastic Approximation theory (SA theory). The theory itself dates back to the fifties since it was first introduced by Robbins and Monro in 1950 [Reference Robbins and Monro24]. Indeed, a stochastic approximation algorithm (an SAA) is defined as follows

$$Z_{n+1}=Z_n + \gamma_{n+1}(h(Z_n)+\Delta M_{n+1}),$$

where $(\gamma _n)_{n\geq 0}$ is a sequence of time steps that decreases almost surely (a.s.) to zero and $(\Delta M_{n})_{n\geq 0}$ is a sequence of remainder terms that depends on the process $Z_n$. In our case, the sequence $(\Delta M_{n})_{n\geq 0}$ is a martingale difference. The primary goal of SA theory is the determination of the set of zeros of the function $h:E \longrightarrow \mathbb {R}$, whose elements, under suitable conditions, are candidates for the almost sure convergence of the process $Z_n$. In this direction, we find the works [Reference Aguech and Selmi1,Reference Aguech, Lasmar and Selmi2,Reference Idriss12,Reference Laruelle and Pagès17Reference Lasmar, Mailler and Selmi19,Reference Renlund22,Reference Renlund23]. In his paper [Reference Renlund22], Renlund highlights the efficiency of SA theory by studying the proportions of each color in an unbalanced $2$-color urn under evolution by both one and two draws. The results of the first paper paved the path to his second paper [Reference Renlund23] in which he establishes one-dimensional limit theorems for the urn composition. We should also point out that, though the models in [Reference Laruelle and Pagès18] are both balanced-in-mean models, the authors relied on SA theory since nonlinear drawing rules exhibits cases where the function $h$ has more than one equilibrium point, some of them are attractors others are repellers, in the sense that for $y^{\star }$ a zero of $h$, if $h(y^{\star })\lt0$ than $y^{\star }$ is called stable and it can be a target for the asymptotic urn composition, otherwise (meaning it is not stable) it is a repeller and unfit to be a limiting point to the urn composition. In [Reference Idriss12], the author manages to retrieve limit laws, an SLLN and a CLT for an irreducible replacement matrix and only an ${\rm a.s.}$ convergence in the case of a reducible replacement matrix.

1.2. Aim of the paper

Inspired and intrigued by the rich archive of GPU, the work in this paper is a combination of two models, the one in [Reference Idriss12] and that in [Reference González-Navarrete and Lambert11]. We extend the model in [Reference Idriss12] to a model involving two concave functions $f_1$ and $f_2$.We also widen the class of these functions by lessening the conditions proposed in [Reference Idriss12]: we allow the functions to be decreasing and change the conditions $f_i(0)=0$ and $f_i(1)=1$ to $f_i(0)\geq 0$ and $f_i(1)\leq 1$. That is the drawn ball is of color $i\in \{1,2\}$ with probability

$$\frac{f_i(Y^i_n)}{f_1(Y_n^1)+f_2(Y_n^2)},\quad n\geq0,$$

where $f_i:[0,1]\longrightarrow [0,1]$ satisfying

$$f_i \ \text{is strictly monotonic and concave}.$$

As a theoretical application of our model, we propose the model of [Reference González-Navarrete and Lambert11]. Since the work in [Reference González-Navarrete and Lambert11] relied on techniques from Janson's papers [Reference Janson14,Reference Janson15], we restudy the model, after dropping the balance condition, using SA theory. The addition rule is a captured in a $2\times 2$ matrix with nonnegative random entries, which is independent from the past, and we view the two drawing strategies as two different drawing rules involving the two functions $f_1$ and $f_2$. We prove an SLLN for the total number of balls and a CLT for the normalized urn composition. In addition, we provide an estimate of the mean and variance of both types of balls. While doing so, we show that, once more, SA theory is a successful tool to study unbalanced urn models, we show as well that, if we reinstate the balance condition in the application model, we retrieve the exact same results as in [Reference González-Navarrete and Lambert11].

1.3. Outline of the article

The end of this section, Section 1.4, is devoted to describing our model. Section 2 consists in setting the ground by enunciating the main conditions and hypothesis, frame the urn composition as an SAA (a stochastic approximation algorithm), and stating some results on SA theory from [Reference Robbins and Monro24] as they are crucial to our work. Once done, we establish in Section 3 our main results on the asymptotic behavior of the urn composition, we give as well an estimate of the mean and variance of both types of balls.

1.4. The model

The model at hand is an extension to the one described in [Reference Idriss12]. While in [Reference Idriss12] the drawing rule does not depend on the color withdrawn, in this model, the rule changes according to the color withdrawn in the following sense:

Consider an urn containing balls of two colors, say white and blue. If a white ball is drawn, we proceed with rule number $1$ and if a blue ball is drawn, thus rule number $2$ is in play.

Let us describe the model under consideration: All random variables involved in this model are supposed to be defined on the same probability space $(\Omega,\mathscr {A},\mathbb {P})$. Denote by $W_n$ and $B_n$ the number of white and blue balls respectively in the urn at time $n$, then $T_n:=W_n+B_n$ represents the total number of balls at that stage.

The following definition is given in [Reference Laruelle and Pagès17] for a single urn that follows a unique nonlinear drawing rule. We state it here in a more general form.

Definition 1.1. A function $f_i:[0,1]\longrightarrow [0,1]$ satisfying the following

(1)\begin{equation} f_i \ \text{is strictly monotonic and concave}, \end{equation}

is called a skewing function.

The functions $(f_i)_{i=1,2}$ may satisfy an additional condition such as concavity. In the sequel, it will be mentioned each time the concavity is needed.

Considering $(\mathscr {F}_n)_{n\geq 0}$ as the $\sigma$-algebra generated by the first $n$ draws, the model is represented as follows:

Let $\textbf {X}_n$ : $(\Omega,\mathscr {A},\mathbb {P}) \longrightarrow \{\textbf {e}_1,\textbf {e}_2\}$ represents the color of the drawn ball at time $n$, i.e., the events $\{\textbf {X}_{n+1}=\textbf {e}_1\}$ and $\{\textbf {X}_{n+1}=\textbf {e}_2\}$ represent respectively the drawing of a white ball and a blue ball. Let $f_1$ and $f_2$ be functions satisfying Definition 1.1. Then the normalized nonlinear drawing rules are given by:

(2)\begin{equation} \mathbb{P}(\textbf{X}_{n+1}=e^1\,|\,\mathscr{F}_{n})= \frac{f_1(\frac{W_n}{T_n})} {f_1(\frac{W_n}{T_n})+f_2(\frac{B_n}{T_n})} \quad \text{and} \quad \mathbb{P}(X_{n+1}=e^2\,|\,\mathscr{F}_{n})= \frac{f_2(\frac{B_n}{T_n})} {f_1(\frac{W_n}{T_n})+f_2(\frac{B_n}{T_n})}. \end{equation}

Given the replacement matrix with nonnegative entries:

(3)\begin{equation} \Sigma_{n}:=\begin{pmatrix} \xi_{n}^{11} & \xi_{n}^{21} \\ \xi_{n}^{12} & \xi_{n}^{22} \end{pmatrix}, \end{equation}

where the entries $(\xi _{n}^{ij})_{n\geq 0}$, for $i,j \in \{1,2\},$ are sequences of i.i.d., positive, bounded random variables, the following stochastic recursion describes the evolution of the urn

\begin{align*} W_{n+1}& =W_n+\sum_{i=1}^{2} \xi_{n+1}^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}},\\ B_{n+1}& =B_n+\sum_{i=1}^{2} \xi_{n+1}^{i2}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}}. \end{align*}

We emphasize that the replacement matrix is independent from the past. Moreover, given $\mathscr {F}_{n-1}$, it is conditionally independent from the drawing procedure $\textbf {X}_n$ for every $n\geq 1$. So, denoting by ${Y_n}: = \left( \matrix{{W_n} \hfill \cr {B_n} \hfill \cr} \right)$, one has

(4)\begin{equation} Y_{n+1}=Y_n+ \Sigma_{n+1} \textbf{X}_{n+1}, \quad n\geq0. \end{equation}

The total number of balls is given by

(5)\begin{equation} T_{n+1}=T_{n}+\| \Sigma_{n+1} \textbf{X}_{n+1} \| = T_n+\sum_{i=1}^{2} \sum_{j=1}^{2}\xi_{n+1}^{ij}{\mathbb{1}} _{\{\textbf{X}_{n+1}=\textbf{e}_i\}}, \end{equation}

where $\|\cdot \|$ denotes the $\ell ^1$ norm.

Note that we do not impose any balance condition on the replacement matrix $\Sigma _n$ and we emphasize that the mean matrix $\Gamma :=\mathbb {E}(\Sigma _{n})$ is not necessarily balanced. That is for $i,j \in \{1,2\}$, if we denote by:

$$\mu^{ij}=\mathbb{E}(\xi_{n}^{ij})\quad \text{and} \quad \mu_i:=\mu^{i1}+\mu^{i2},\quad i\in\{1,2\},$$

then the mean matrix given by:

(6)\begin{equation} \Gamma=\begin{pmatrix} \mu^{11} & \mu^{21} \\ \mu^{12} & \mu^{22} \end{pmatrix}, \end{equation}

satisfies

(7)\begin{equation} \mu_1\neq \mu_2. \end{equation}

Finally, we denote the second moments by

(8)\begin{equation} \sigma^{ij}=\mathbb{V}{\rm ar}(\xi_{n}^{ij}). \end{equation}

The aim of the study of urn models throughout history is to investigates the asymptotic behavior of the urn composition and establish asymptotic estimations for the moments of the number of balls of each color (see [Reference Janson14,Reference Mahmoud21] ). Toward that end, we need to set the following assumptions:

  1. (A1) For all $i \in \{1,2\}, f_i$ is a skewing function and differentiable on $(0,1)$.

  2. (A2) The urn scheme is tenable. It means that as long as the process is running, the urn never comes to a halt.

  3. (A3) The mean matrix $\Gamma$ is not necessarily balanced, that is, $\mu ^{11}+\mu ^{12}\neq \mu ^{21}+\mu ^{22}$ for all $n\geq 0$.

  4. (A4) There exist positive constants $p^{ij}$ and $q^{ij}$ such that for all $i,j \in \{1,2\},$ one has $p^{ij}\leq \xi _n^{ij}\leq q^{ij}$ for all $n\geq 0$.

  5. (A5) The addition rule $\Sigma _n$ and the drawing procedure $\textbf {X}_n$ are conditionally independent given $\mathscr {F}_{n-1}$ for every $n\geq 1$.

Henceforth, we adopt the following notation. For $y=(y^1,y^2) \in \mathbb {R}^2$, we have

  • $y'$ denotes the column vector.

  • $\|y\|=|y^1|+|y^2|$ denotes the $\ell ^1$ norm.

  • Let $h$ be a function defined on a set $G$ then for $A\subseteq G$, $h_{|A}$ denotes the restriction of the function $h$ to A.

  • $\Theta ^\star :=\{y\in [0,1]: h(y)=0\}$ denotes the set of zeros of the function $h$.

2. Skewed bi-dimensional nonlinear urn model

2.1. Some results on stochastic approximation algorithm

We give in this section some basic tools that will come in handy in the proofs of our main results. These tools, originally introduced in Robbins and Monro [Reference Robbins and Monro24], were later developed by Renlund [Reference Renlund22,Reference Renlund23] within the framework of urn models.

Definition 2.1. A stochastic approximation algorithm $(Z_n)_{n\geq 0}$ is a stochastic process taking values in $[0,1]$, adapted to the filtration $\mathscr {F}_n$, that satisfies

$$Z_{n+1}-Z_n=\gamma_{n+1}(h(Z_n)+M_{n+1}),$$

where $\gamma _n$, $M_n\in \mathscr {F}_n$, $h:[0,1]\longrightarrow \mathbb {R}$ and the following conditions hold almost surely:

  1. (i) ${c_1}/{n}\leq \gamma _n \leq {c_2}/{n}$,

  2. (ii) $|M_n|\leq K_u$,

  3. (iii) $|h(Z_n)|\leq K_h$,

  4. (iv) $|\mathbb {E}[\gamma _{n+1}M_{n+1}\,|\, \mathscr {F}_n]| \leq K_e\gamma _n^2$.

where the constants $c_1, c_2, K_u, K_h$ and $K_e$ are positive real numbers.

Definition 2.2. Let $\Theta ^\star :=\{y\in [0,1]: h(y)=0\}$, where $h$ is given in Definition 2.1. A zero $y^\star$ of $h$ is called $stable$ if $h$ is differentiable and $h'(y^\star )\lt0$. Otherwise it is called $unstable$.

Proposition 2.1. Let $(Z_n)_{n\geq 0}$ be a stochastic algorithm defined as in Definition 2.1. If $h$ is continuous, then $Z_n$ converges almost surely to a stable zero of $h$.

Theorem 2.1. Let $(Q_n)_{n\geq 0}$ be a stochastic process adapted to a filtration $\{\mathscr {F}_n, n\geq 0\}$, such that

$$Q_{n+1}=\left(1-\frac{\hat{\gamma}_{n+1}}{n+1}\right)Q_n+\frac{U_{n+1}}{n+1},$$

where $\hat {\gamma }_n,\; U_n \in \mathscr {F}_n$. Assume that, one has almost surely:

  1. 1. $\hat {\gamma }_n \longrightarrow \hat {\gamma } \gt\frac {1}{2}$.

  2. 2. $\mathbb {E}((U_n)^2\,|\,\mathscr {F}_{n-1}) \longrightarrow \sigma ^2$.

Then one has,

$$\sqrt{n}Q_n \overset{\mathscr{D}}{\longrightarrow} \mathscr{N}\left(0,\frac{\sigma^2}{2\hat{\gamma}-1}\right).$$

2.2. Representation as a stochastic algorithm

We start by formulating the urn dynamics (2)(5) as a stochastic process approximation. Since our model is $2$-dimensional, it suffices to work with only one of the two proportions of colors.

In what follows, we will use the following notation:

\begin{align*} Z_n& :=\frac{W_n}{T_n},\\ \xi_{n+1}^1& := \xi_{n+1}^{11}+\xi_{n+1}^{12}\quad \text{and} \quad \xi_{n+1}^2:=\xi_{n+1}^{21}+\xi_{n+1}^{22}. \end{align*}

So, under assumption A(5), we have the following:

\begin{align*} Z_{n+1}-Z_{n}& =\frac{W_{n+1}}{T_{n+1}}-\frac{W_{n}}{T_{n}}\\ & =\frac{1}{T_{n+1}}\left(W_n+ \sum_{i=1}^{2} \xi_{n+1}^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1} =\textbf{e}_i\}}- \left(T_{n}+\| \Sigma_{n+1}\textbf{X}_{n+1} \| \right)\frac{W_n}{T_n}\right)\\ & =\frac{1}{T_{n+1}}\left(\sum_{i=1}^{2} \xi_{n+1}^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}}-Z_n \left(\sum_{i=1}^{2} \sum_{j=1}^{2}\xi_{n+1}^{ij}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}} \right)\right)\\ & =\frac{1}{T_{n+1}}((\xi_{n+1}^{11}-\xi_{n+1}^1Z_n){\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}+ (\xi_{n+1}^{21}-\xi_{n+1}^2Z_n){\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}} ). \end{align*}

Denoting by

$$L_{n+1}:=(\xi_{n+1}^{11}-\xi_{n+1}^1Z_n){\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}+ (\xi_{n+1}^{21}-\xi_{n+1}^2Z_n){\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}},$$

then, we have

$$\mathbb{E}(L_{n+1}\,|\,\mathscr{F}_n)=\mathbb{E}((\xi_{n+1}^{11}-\xi_{n+1}^1Z_n){\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}+ (\xi_{n+1}^{21}-\xi_{n+1}^2Z_n){\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}|\mathscr{F}_n),$$

which yields:

$$\mathbb{E}(L_{n+1}\,|\,\mathscr{F}_n)=\frac{(\mu^{11}-\mu_1Z_n)f_1(Z_n)+ (\mu^{21}-\mu_2Z_n)f_2(1-Z_n)}{f_1(Z_n)+f_2(1-Z_n)}.$$

So, writing the stochastic recursion in the following form

$$Z_{n+1}-Z_{n}=\frac{\mathbb{E}(L_{n+1}\,|\,\mathscr{F}_n)+ L_{n+1}-\mathbb{E}(L_{n+1}\,|\,\mathscr{F}_n)}{T_{n+1}},$$

one has

(9)\begin{equation} Z_{n+1}=Z_n+\gamma_{n+1}(h(Z_n)+\Delta M_{n+1}), \end{equation}

where

$$\gamma_{n+1}=\frac{1}{T_{n+1}},$$

the function

(10)\begin{equation} h(y)=\frac{(\mu^{11}-y\mu_1)f_1(y)+(\mu^{21}-y\mu_2)f_2(1-y)}{f_1(y)+f_2(1-y)}, \quad y\in [0,1], \end{equation}

is the mean field where $h:[0,1]\mapsto [0,1]$, $f_1,f_2$ satisfy (1) and $(\mu ^{ij})_{(1\leq i,j\leq 2)}$, $(\mu _i)_{i=1,2}$ are given by (6)(7). and finally,

(11)\begin{equation} \Delta M_{n+1}=L_{n+1}-\mathbb{E}(L_{n+1}|\mathscr{F}_n), \end{equation}

is an adapted martingale difference.

2.3. Existence of equilibrium points

Proposition 2.2. (Existence)

Let $h$ be as in (10). Then the set $\Theta ^\star$ is nonempty and $\Theta ^\star$ is a subset of the interval

$$\left[\min\left(\frac{\mu^{11}}{\mu_1},\frac{\mu^{21}}{\mu_2}\right), \max\left(\frac{\mu^{11}}{\mu_1},\frac{\mu^{21}}{\mu_2}\right)\right].$$

Proof. The function $h$ is continuous. Moreover one has

$$h(0)=\frac{\mu^{11}f_1(0)+\mu^{21}f_2(1)}{f_1(0)+f_2(1)}\gt0,$$

and

$$h(1)=\frac{-\mu^{12}f_1(1)-\mu^{22}f_2(0)}{f_1(1)+f_2(0)}\lt0,$$

then $h$ has at least one zero in $(0,1)$. Let us show that:

$$\text{for all} \quad y\notin \left[\min\left(\frac{\mu^{11}}{\mu_1},\frac{\mu^{21}}{\mu_2}\right) ,\max\left(\frac{\mu^{11}}{\mu_1},\frac{\mu^{21}}{\mu_2}\right)\right],\quad \text{one has} \ h(y)\neq 0.$$

Indeed, since the mean field $h$ can read as follows:

$$h(y)=\frac{\mu_1(\frac{\mu^{11}}{\mu_1}-y)f_1(y)+ \mu_2(\frac{\mu^{21}}{\mu_2}-yf_2(1-y)}{f_1(y)+f_2(1-y)},$$

then it is easy to see that $h(y)\gt0$ if $0\leq y\lt\min ({\mu ^{11}}/{\mu _1},{\mu ^{21}}/{\mu _2})$ and that $h(y)\lt0$ if $\max ({\mu ^{11}}/{\mu _1},{\mu ^{21}}/{\mu _2})\lt y\leq 1$.

Proposition 2.3. (Counting equilibrium points)

Under the assumptions (A1)–(A3), $h$ has a unique equilibrium point if the following conditions hold:

  1. 1. If $\bar {\mu }:={\mu ^{11}}/{\mu _1}={\mu ^{21}}/{\mu _2}$, then $\bar {\mu }$ is the unique zero of $h$.

  2. 2. In the case where ${\mu ^{11}}/{\mu _1}\lt{\mu ^{21}}/{\mu _2}$, one of the following conditions is satisfied:

    1. (a 1) Both $f_1$ and $f_2$ are increasing.

    2. (b 1) Both $f_1$ and $f_2$ are decreasing and concave.

  3. 3. In the case where ${\mu ^{11}}/{\mu _1}\gt {\mu ^{21}}/{\mu _2}$, one of the following conditions is satisfied:

    1. (a 2) Both $f_1$ and $f_2$ are increasing and concave.

    2. (b 2) Both $f_1$ and $f_2$ are decreasing.

Proof. We will only prove the second assertion, as the uniqueness of the zero is obvious in the first assertion, and for the third assertion, the proof is similar to that of the second one. Hence, suppose that ${\mu ^{11}}/{\mu _1}\lt{\mu ^{21}}/{\mu _2}$, and suppose that both $f_1$ and $f_2$ are increasing. Since

$$h(y)=0 \ \Leftrightarrow \ K(y)=L(y).$$

where

$$K(y)=(\mu^{11}-y\mu_1)f_1(y)\quad \text{and}\quad L(y)={-}(\mu^{21}-y\mu_2)f_2(1-y),$$

then

$$K(y)=L(y)\ \Leftrightarrow \ g_1(y)=g_2(y),$$

where

$$g_1(y)=\frac{f_2(1-y)}{\mu^{11}-y\mu_1},\quad y\in [0,1]\setminus \{\tfrac{\mu^{11}}{\mu_1}\}$$

and

$$g_2(y)=\frac{f_1(y)}{y\mu_2-\mu^{21}},\quad y\in [0,1]\setminus \{\tfrac{\mu^{21}}{\mu_2}\}.$$

Let us show that

$$\{g_1=g_2\}\cap \left[\min\left(\frac{\mu^{11}}{\mu_1},\frac{\mu^{21}}{\mu_2}\right) ,\max\left(\frac{\mu^{11}}{\mu_1},\frac{\mu^{21}}{\mu_2}\right)\right] \neq \emptyset.$$

By assumption (A1), the functions $f_1$ and $f_2$ are assumed to be differentiable on $(0,1)$, so the derivatives of $g_1$ and $g_2$ are as follows

$$g'_1(y)=\frac{-f_2'(1-y)(\mu^{11}-y\mu_1)+\mu_1f_2(1-y)}{(\mu^{11}-y\mu_1)^2},$$

and

$$g'_2(y)=\frac{f'_1(y)(\mu_2y-\mu^{12})-\mu_2f_1(y)}{(y\mu_2-\mu^{12})^2}.$$

The fact that $(\mu ^{11}-y\mu _1)\lt0$ and $(\mu _2y-\mu ^{12})\gt0$ plus the fact that both $f'_1$ and $f'_2$ are positive, yield $g'_1(y)\geq 0$ and $g'_2(y)\leq 0$. This proves $(a_1)$.

As for $(b_1)$, both $f_1$ and $f_2$ are concave, and so $f_1(y)-yf_1'(y)\geq 0$ and $f_2(1-y)-(1-y)f_2'(1-y)\geq 0$. Hence, writing the derivatives of $g_1$ and $g_2$ in the following form

\begin{align*} g'_1(y)& =\frac{\mu_1(f_2(1-y)-(1-y)f_2'(1-y))+(\mu_1-\mu^{11})f_2(1-y)}{(\mu^{11}-y\mu_1)^2},\\ g'_2(y)& =\frac{\mu_2(yf_1'(y)-f_1(y))-\mu^{21}f(y)}{(y\mu_2-\mu^{21})^2}, \end{align*}

ensures that $g'_1(y)\geq 0$ and $g'_2(y)\leq 0$.

Proposition 2.4. (Stable equilibrium point)

Let $h$ be as in (10). Then under assumption (A1), if $h$ has a unique equilibrium point then it is stable.

Proof. Based on Definition 2.2, a zero $y^\star$ of $h$ is stable if and only if $h$ is differentiable and $h'(y^\star )\lt0$. To investigate this we recall that $h(0)=\mu ^{21}\gt0$ and $h(1)=-\mu ^{12}\lt0$. By assumption (A1), $h$ is differentiable on $(0,1)$. Since $h$ has only one zero $y^\star$ in $(0,1)$, then $h$ changes its sign with respect to $y^\star$, which means that there exists $\epsilon \gt0$ small enough such that $h_{\mid (y^\star -\epsilon,y^\star )}\gt0$ and $h_{\mid (y^\star,y^\star +\epsilon )}\lt0$. In other words $h_{\mid (y^\star -\epsilon,y^\star +\epsilon )}$ is strictly decreasing therefore $h'(y^\star )\lt0$.

Example 2.1. (Connection to previous models)

We give this example in order to elucidate the link between the present model and other previous models. Recall that our model involves two different nonlinear drawing rules involving two functions $f_1$ and $f_2$ along with a randomized replacement matrices $(\Sigma _n)_{n\geq 0}$. We mention them here for the convenience of the reader:

The mean field is given by

$$h(y)=\frac{(\mu^{11}-y\mu_1)f_1(y)+(\mu^{21}-y\mu_2)f_2(1-y)}{f_1(y)+f_2(1-y)}, \quad y\in [0,1],$$

where $f_i:[0,1] \longrightarrow [0,1]$ satisfying, for all $i \in \{1,2\},$ the following:

$$f_i\ \text{is strictly monotonic and concave},$$

and the constants $\mu ^{ij}=\mathbb {E}(\xi ^{ij})$, $\mu _1:=\mu ^{11}+\mu ^{12}\neq \mu _2:=\mu ^{21}+\mu ^{22}$ with $(\xi _n^{ij})_{1\leq i,j \leq,2}$ are the entries of the random replacement matrix $(\Sigma _n)_{n\geq 0}$. Basically, we show in this example how one can transition from our model to some other models by adjusting the conditions imposed on our model. Hence, we have:

  1. 1. If $f_1\equiv f_2 \equiv f$ where $f$ is non-decreasing, $f(0)=0$, $f(1)=1$, $\{f\gt0\}=(0,1]$ and:

    • if the addition matrices $(\Sigma _n)_{n\geq 0}$ are co-stochastic, i.e. $\mu _1=\mu _2=1$, then the mean field would be as follows:

      $$h(y)=\frac{\mu^{11}f(y)+\mu^{21}f(1-y)}{f(y)+f(1-y)}-y.$$
      Hence, we recover the model introduced in [Reference Laruelle and Pagès17] after a normalization with the balance constant and if we set the multi-colored urn in [Reference Laruelle and Pagès17] to a two-colored urn.
    • If the addition matrices are deterministic and unbalanced we retrieve the model in [Reference Idriss12].

  2. 2. If $f_1\equiv f_2 \equiv id_{[0,1]}$ and if the matrices $(\Sigma _n)_{n\geq 0}$ are deterministic with:

    • $\xi _n^{11}=\xi _n^{22}=0$, and $\xi _n^{21}=a\neq \xi _n^{12}=b$, for all $n\geq 0$, the mean field becomes then

      $$h(y)=(a-b)y^2-2ay+a.$$
    • $\xi _n^{21}=\xi _n^{12}=0$, and $\xi _n^{11}=a\neq \xi _n^{22}=b$, for all $n\geq 0$, then the mean field becomes as follows:

      $$h(y)=(a-b)y(1-y).$$

    Therefore, we retrieve both opposite and self reinforcing models studied in [Reference Aguech, Lasmar and Selmi2] once we set the multi-draw in [Reference Aguech, Lasmar and Selmi2] to a single draw.

Example 2.2. In this example we illustrate the existence and uniqueness of the equilibrium point by considering the following functions, for all $y\in [0,1]$,

$$f_1(y)=\ln(y+1.25);\quad f_2(y)=0.7y+0.2$$

and

$$g_1(y)={-}0.5y^2-0.3y+0.9; \quad g_2(y)={-}y^2+1.$$

The functions $f_1$, $f_2$, $g_1$ and $g_2$ satisfy Definition 1.1. Indeed we have:

  • $f_1$ and $f_2$ are both increasing and concave. Moreover one has

    $$f_1(0)\approx0.23, \quad f_1(1)\approx0.81 \quad \text{and} \quad f_2(0)=0.2,\quad f_2(1)=0.9.$$
  • $g_1$ and $g_2$ are both decreasing and concave. Moreover one has

    $$g_1(0)=0.9, \quad g_1(1)=0.1 \quad \text{and} \quad g_2(0)=1,\quad g_2(1)=0.$$

Notice that both conditions $(a_1)$ and $(a_2)$ of Proposition 2.3 are satisfied by the functions $f_1$ and $f_2$ and both conditions $(b_1)$ and $(b_2)$ of Proposition 2.3 are satisfied by the functions $g_1$ and $g_2$.

Now, let us specify the replacement matrix. We choose a deterministic unbalanced matrix as follows:

$$\Sigma:=\begin{pmatrix} 2 & 1 \\ 3 & 2 \end{pmatrix}.$$

Hence, the figure on the left represents the graph of the mean field $h$ involving the functions $f_1$ and $f_2$ while the one on the right represents the graph of the mean field involving the functions $g_1$ and $g_2$. Existence and uniqueness of the equilibrium point in both cases we get a unique stable zero (Figure 1).

FIGURE 1. Examples of the function $h$.

Theorem 2.2. (A.s. convergence)

Let $Z_n$ be as in (9). Then under assumptions (A1)–(A5), $Z_n$ converges almost surely to $y^\star$.

Proof. To ensure the almost sure convergence, we need to satisfy the assumptions of Definition 2.2. Indeed one has:

  1. 1. ${c_1}/{n} \leq {1}/{T_n} \leq {c_2}/{n}$. Due to the relation (5) one has:

    $$T_n= T_0 +\sum_{\ell=1}^{n} \sum_{i=1}^{2} \sum_{j=1}^{2}\xi_{\ell}^{ij}{\mathbb{1}}_{\{\textbf{X}_{\ell}=\textbf{e}_i\}},$$
    so that
    $$T_0+ 4 n \min_{i,j}(p^{ij})\leq T_n \leq T_0 + 4 n \max_{i,j}(q^{ij}).$$
  2. 2. $|h(y)| \leq K_h$. In fact, one has

    \begin{align*} | h(Z_n)|& =|(\mu^{11}-Z_n\mu_1)\mathbb{P}(\textbf{X}_{n+1}=\textbf{e}_1|\mathscr{F}_n) +(\mu^{21}-Z_n\mu_2)(\mathbb{P}(\textbf{X}_{n+1}=\textbf{e}_2|\mathscr{F}_n))|\\ & \leq |(\mu^{11}-Z_n\mu_1)|+ | (\mu^{21}-Z_n\mu_2) |\\ & \leq 2|\mu_1+ \mu_2|. \end{align*}
  3. 3. $|\Delta M_{n+1}| \leq K_M$. Indeed, one has

    \begin{align*} |\Delta M_{n+1}|& \leq | L_{n+1} | + |\mathbb{E}(L_{n+1}|\mathscr{F}_n)|\\ & \leq 2 \left(4 \max_{i,j}(q^{ij})+|\mu_1 + \mu_2| \right). \end{align*}
  4. 4. $|\mathbb {E}[{\Delta M_{n+1}}/{T_{n+1}}| \mathscr {F}_n]|\leq {K_e}/{T_n^2}$. Owing to relations (5), (10)(11), one has

    \begin{align*} \frac{\Delta M_{n+1}}{T_{n+1}} & =\frac{L_{n+1}-\mathbb{E}(L_{n+1}\,|\,\mathscr{F}_n)}{T_n+ \xi_{n+1}^1 {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}+\xi_{n+1}^2 {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}}\\ & =\frac{(\xi_{n+1}^{11}-Z_n\xi_{n+1}^1)-h(Z_n)}{T_n+ \xi_{n+1}^1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}\\ & \quad +\frac{(\xi_{n+1}^{21}-Z_n\xi_{n+1}^2)-h(Z_n)}{T_n+ \xi_{n+1}^2}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}\\ & = (T_n+\xi_{n+1}^2)\frac{(\xi_{n+1}^{11}-Z_n\xi^1_{n+1})-h(Z_n)}{(T_n+ \xi_{n+1}^1)(T_n+ \xi_{n+1}^2)} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}\\ & \quad +(T_n+ \xi_{n+1}^1)\frac{(\xi_{n+1}^{21}-Z_n\xi^2_{n+1})-h(Z_n)}{(T_n+ \xi_{n+1}^1)(T_n+ \xi_{n+1}^2)} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}\\ & \leq(T_n+ \xi_{n+1}^2)\frac{(\xi_{n+1}^{11}-Z_n\xi_{n+1}^1)-h(Z_n)}{T^2_n} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}\\ & \quad +(T_n+\xi_{n+1}^1)\frac{(\xi_{n+1}^{21}-Z_n\xi_{n+1}^2)-h(Z_n)}{T_n^2} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}. \end{align*}
    Hence, we have
    \begin{align*} \left|\mathbb{E}\left[\left.\frac{\Delta M_{n+1}}{T_{n+1}}\right|\mathscr{F}_n\right]\right| & \leq \left| \mathbb{E}\left[(T_n+ \xi_{n+1}^2)\left.\frac{(\xi_{n+1}^{11}-Z_n\xi_{n+1}^1)-h(Z_n)} {T_n^2}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}\right|\mathscr{F}_n\right]\right.\\ & \quad +\left.\mathbb{E}\left[(T_n+ \xi^1_{n+1})\left.\frac{(\xi_{n+1}^{21}-Z_n\xi^2_{n+1})-h(Z_n)}{T_n^2} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}\right|\mathscr{F}_n\right]\right| \\ & \leq\left|((\mu^{11}-\mu_1Z_n)-h(Z_n))\mathbb{P}(\textbf{X}_{n+1}=\textbf{e}_1\,|\,\mathscr{F}_n) \frac{T_n+\mu_2}{T_n^2}\right.\\ & \quad +\left.((\mu^{21}-\mu_2Z_n)-h(Z_n))\mathbb{P}(\textbf{X}_{n+1}=\textbf{e}_2\,|\,\mathscr{F}_n) \frac{T_n+\mu_1}{T_n^2}\right|\\ & \leq|(\mu^{11}-\mu_1Z_n)-(\mu^{21}-\mu_2Z_n)|\\ & \quad \times \mathbb{P}(\textbf{X}_{n+1}=\textbf{e}_1\,|\,\mathscr{F}_n) \mathbb{P}(\textbf{X}_{n+1}=\textbf{e}_2\,|\,\mathscr{F}_n)\frac{|\mu_1-\mu_2|}{T_n^2}\\ & \leq\frac{K_M}{T_n^2}. \end{align*}

3. Limit theorems

3.1. Boundedness of the normalized urn composition

Since the replacement matrix is not necessarily balanced, the total number of balls is potentially random, for this reason we need to investigate its rate of convergence. It follows from (4) that

\begin{align*} Y_{n+1}& =Y_n+\mathbb{E}(\Sigma_{n+1} \textbf{X}_{n+1}\,|\,\mathscr{F}_n)+\Delta \tilde{M}_{n+1}\\ & =Y_n+\Gamma\frac{(f_1(Z_n),f_2(1-Z_n))'}{f_1(Z_n)+f_2(1-Z_n)}+\Delta \tilde{M}_{n+1}, \end{align*}

where

(12)\begin{equation} \Delta \tilde{M}_{n+1}:=\Sigma_{n+1} \textbf{X}_{n+1}-\mathbb{E}(\Sigma_{n+1} \textbf{X}_{n+1}|\mathscr{F}_n). \end{equation}

This calculation yields

(13)\begin{align} T_{n+1}& =T_n+ \left|\left| \Gamma \frac{(f_1(Z_n),f_2(1-Z_n))'}{f_1(Z_n)+f_2(1-Z_n)}\right|\right| +\|\Delta \tilde{M}_{n+1} \|\nonumber\\ & =T_n+\frac{\mu_1f_1(Z_n)+\mu_2f_2(1-Z_n)}{f_1(Z_n)+f_2(1-Z_n)}+ \|\Delta \tilde{M}_{n+1}\|. \end{align}

Proposition 3.1. Let $(Y_n)_{n\geq 0}$ be the urn composition defined in (4). Then under (A1)–(A5) we have

(14)\begin{equation} \frac{T_n}{n}\overset{{\rm a.s.}}{\longrightarrow} \frac{\mu_1f_1(y^\star)+\mu_2f_2(1-y^\star)}{f_1(y^\star)+f_2(1-y^\star)}. \end{equation}

Proof. Based on relation (13), one has

$$\frac{T_n}{n}= \frac{T_0}{n}+\frac{1}{n}\sum_{\ell=1}^{n} \frac{\mu_1f_1(Z_\ell)+\mu_2f_2(1-Z_\ell)}{f_1(Z_\ell)+f_2(1-Z_\ell)}+\frac{1}{n} \sum_{\ell=1}^{n} \|\Delta \tilde{M}_{\ell} \|.$$

Since,

\begin{align*} \mathbb{E}(\|\Delta \tilde{M}_{\ell}\|^2\,|\,\mathscr{F}_{\ell-1}) & \leq\mathbb{E}(\| \Sigma_{\ell} X_\ell\|^2\,|\,\mathscr{F}_{\ell-1})+ 3\mathbb{E}(\|\Sigma_{\ell} X_\ell\| \,|\,\mathscr{F}_{\ell-1})^2\\ & \leq4 \mathbb{E}(\|\Sigma_{\ell} \textbf{X}_\ell\|^2\,|\,\mathscr{F}_{\ell-1})\\ & \leq4 \sup_{\ell\geq1} \sup_{j=1,2} \mathbb{E}(\|\Sigma_{\ell} ^{.j}\|^2)\\ & \lt\infty. \end{align*}

Therefore by the $SLLN$ for conditionally $L^2$-bounded martingales, we have: $({1}/{n})\sum _{\ell =1}^{n} \|\Delta \tilde {M}_{\ell } \|\overset {{\rm a.s.}}{\longrightarrow } 0$.

Now, using the fact that both $f_1$ and $f_2$ are continuous on $[0,1]$ and by Cesàro's lemma, we conclude the proof.

Corollary 3.1. Under assumptions (A1)–(A3) and (A5) the mean of the number of white balls satisfies the following estimate:

$$\mathbb{E}(W_n)=n \frac{\mu^{11}f_1(y^\star)+\mu^{21}f_2(1-y^\star)} {f_1(y^\star)+f_2(1-y^\star)}+o(n).$$

Proof. Recall that

$$W_{n+1}=W_n+ \sum_{i=1}^{2} \xi_{n+1}^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}},$$

so, the normalized number of white balls at time $n$ can read as follows:

$$\frac{W_n}{n}= \frac{W_0}{n}+\frac{1}{n}\sum_{\ell=1}^{n} \frac{\mu^{11}f_1(Z_\ell)+\mu^{21}f_2(1-Z_\ell)}{f_1(Z_\ell)+f_2(1-Z_\ell)}+\frac{1}{n}\sum_{\ell=1}^{n} \Delta \tilde{M}^1_{\ell}.$$

where $\Delta \tilde {M}^1_{n}$ is the $1^{st}$ coordinate of the column vector $\Delta \tilde {M}_{n}$ defined in (12). Therefore, following the same approach of the proof of relation (14) we get the desired result.

Corollary 3.2. Under assumptions (A1)–(A3) and (A5) the variance of the number of white balls satisfies the following estimate:

$$\mathbb{V}{\rm ar}(W_{n})=n\frac{G(y^\star)}{(1-F(y^\star))}+o(n),$$

where

\begin{align*} F(y^\star)& :=\frac{2(\mu^{11}-\mu^{21})f_1(y^\star)} {y^\star (\mu_1f_1(y^\star)+\mu_2f_2(1-y^\star))},\\ G(y^\star)& :=\left((\sigma^{11}-\sigma^{21})+(\mu^{11}-\mu^{21})^2\right) \frac{f_1(y^\star)}{f_1(y^\star)+f_2(1-y^\star)}\\ & \quad -(\mu^{11}-\mu^{21})^2\left(\frac{f_1(y^\star)}{f_1(y^\star)+f_2(1-y^\star)}\right)^2 +\sigma^{21}. \end{align*}

Proof.

(15)\begin{align} \mathbb{V}{\rm ar}(W_{n+1})& = \mathbb{V}{\rm ar}(W_n)+\mathbb{V}{\rm ar}\left(\sum_{i=1}^{2} \xi_{n+1}^{i1} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}}\right) \nonumber\\ & \quad +2\sum_{i=1}^{2} \mathbb{C}{\rm ov}(W_n,\xi_{n+1}^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}}). \end{align}

On one hand, one has

(16)\begin{align} \mathbb{V}{\rm ar}\left(\sum_{i=1}^{2} \xi_{n+1}^{i1} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}}\right)& =\mathbb{V}{\rm ar}(\xi_{n+1}^{11} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}})+ \mathbb{V}{\rm ar}(\xi_{n+1}^{21}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}) \nonumber\\ & \quad +2\mathbb{C}{\rm ov}(\xi_{n+1}^{11}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}, \xi_{n+1}^{21}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}). \end{align}

Computations show that,

(17)\begin{align} \mathbb{V}{\rm ar}(\xi_{n+1}^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}})& = (\sigma^{i1}+(\mu^{i1})^2)\mathbb{E}\left(\frac{f_i(Z_n^i)}{f_1(Z_n^1)+f_2(Z_n^2)}\right) \nonumber\\ & \quad -(\mu^{i1})^2\mathbb{E}\left(\frac{f_i(Z_n^i)}{f_1(Z_n^1)+f_2(Z_n^2)}\right)^2, \end{align}

where for $i=1$, one has $Z_n^1:={W_n}/{T_n}$ and for $i=2$, one has $Z_n^2:={B_n}/{T_n}$.

The third term in (16) is given by:

(18)\begin{align} & \mathbb{C}{\rm ov}(\xi_{n+1}^{11}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}}, \xi_{n+1}^{21}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}})\nonumber\\ & \quad ={-}2\mu^{11}\mu^{21} \mathbb{E}\left(\frac{f_1(Z^1_n)}{f_1(Z_n^1)+f_2(Z_n^2)}\right) \mathbb{E}\left(\frac{f_2(Z^2_n)}{f_1(Z_n^1)+f_2(Z_n^2)}\right). \end{align}

Now, letting $n$ tend to infinity in relations (17) and (18), relation (16) becomes then

(19)\begin{align} \mathbb{V}{\rm ar}(\sum_{i=1}^{2} \xi_{n+1}^{i1} {\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}})& =(\sigma^{11}-\sigma^{21}+(\mu^{11}-\mu^{21})^2) \frac{f_1(y^\star)}{f_1(y^\star) +f_2(1-y^\star)} \nonumber\\ & \quad -(\mu^{11}-\mu^{21})^2 \left(\frac{f_1(y^\star)}{f_1(y^\star)+f_2(1-y^\star)}\right)^2 +\sigma^{21}+o(1). \end{align}

On the other hand, for $i\in \{1,2\}$, one has

$$\mathbb{C}{\rm ov}(W_n,\xi_{n+1}^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}}) =\mathbb{C}{\rm ov}\left(W_n,\frac{\mu^{i1}f_i(Z_n^i)} {f_1(Z_n^1)+f_2(Z_n^2)}\right),$$

which gives us

$$\sum_{i=1}^{2} \mathbb{C}{\rm ov}(W_n,\xi_{n+1}^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}}) =(\mu^{11}-\mu^{21})\,\mathbb{C}{\rm ov}(W_n,W_n\cdot H_n),$$

where

$$H_n:=\frac{1}{Z^1_n}\times\frac{1}{T_n}\times\frac{f_1(Z_n^1)}{f_1(Z_n^1)+f_2(Z_n^2)}.$$

Using relation (14) and Theorem 2.2 we get

$$H_n=\frac{f_1(y^\star)} {n y^\star (\mu_1f_1(y^\star)+\mu_2f_2(1-y^\star))}(1+o(1)),$$

yielding

(20)\begin{equation} \sum_{i=1}^{2} \mathbb{C}{\rm ov}(W_n,\xi^{i1}{\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_i\}}) =\left(\frac{(\mu^{11}-\mu^{21})f_1(y^\star)} {ny^\star (\mu_1f_1(y^\star)+\mu_2f_2(1-y^\star))}(1+o(1))\right)\mathbb{V}{\rm ar}(W_n). \end{equation}

In view of relations (19) and (20), relation (15) becomes then as follows:

(21)\begin{equation} \mathbb{V}{\rm ar}(W_{n+1})=\lambda_n\mathbb{V}{\rm ar}(W_n)+\delta_n, \end{equation}

where

$$\lambda_n:=\left(1+\frac{F(y^\star)}{n}(1+o(1))\right) \quad \text{and}\quad \delta_n:=G(y^\star)+o(1).$$

Thus by recurrence, relation (21) becomes

$$\mathbb{V}{\rm ar}(W_{n})=\prod_{k=0}^{n-1}\lambda_k\left(\mathbb{V}{\rm ar}(W_{0})+ \sum_{k=0}^{n-1}\frac{\delta_k}{\prod_{\ell=1}^{k}\lambda_\ell}\right),$$

so, there exists a positive constant $\lambda$ such that

$$\prod_{k=0}^{n-1}\lambda_k=\lambda n^{F(y^\star)}(1+o(1)),$$

and

$$\sum_{k=0}^{n-1}\frac{\delta_k}{\prod_{\ell=1}^{k}\lambda_\ell} =n^{1-F(y^\star)}\frac{G(y^\star)}{\lambda(1-F(y^\star))}+o(n).$$

Finally, one gets

$$\mathbb{V}{\rm ar}(W_{n})=n\frac{G(y^\star)}{(1-F(y^\star))}+o(n).$$

Example 3.1. [Reference Aguech, Lasmar and Selmi2]

Suppose that the replacement matrix is as follows:

$$\Sigma:=\begin{pmatrix} 0 & a \\ b & 0 \end{pmatrix},$$

where $a,b\geq 0$ and $a\neq b$. Then the mean and variance of the number of white balls satisfy:

$$\mathbb{E}(W_n)=n\sqrt{a b}y^\star{+}o(n) \quad \text{and} \quad \mathbb{V}{\rm ar}(W_n)=n\frac{a^2y^\star(1-y^\star)^2}{1+y^\star}+o(n),$$

where $y^\star ={\sqrt {a}}/{(\sqrt {a}+\sqrt {b})}$ is the ${\rm a.s.}$ limit point for the proportion of white balls.

Example 3.2. [Reference Bagchi and Pal3]

Suppose that the replacement matrix is as follows:

$$\Sigma:=\begin{pmatrix} a & c \\ b & d \end{pmatrix}, \quad a,b,c,d\geq0,$$

we suppose in addition that the matrix is balanced, i.e. $a+b=c+d=K$. Then the mean and variance of the number of white balls satisfy:

$$\mathbb{E}(W_n)=nK x^\star{+}o(n) \quad \text{and} \quad \mathbb{V}{\rm ar}(W_n)=nK\frac{(a-c)^2x^\star(1-x^\star)}{K-2(a-c)}+o(n),$$

where $x^\star ={c}/{(c+b)}$ is the ${\rm a.s.}$ limiting point for the proportion of white balls.

3.2. Weak convergence

In this section, we establish a CLT for the urn composition $(Z_n)_{n\geq 0}$ on the event $\{Z_n\rightarrow y^\star \}$.

Theorem 3.1. Let us set

$$\hat{\gamma}:=1-\rho^\star,$$

where

$$\rho^\star:=\frac{(\mu^{11}-y^\star \mu_1)f_1'(y^\star)-(\mu^{21}-y^\star \mu_2)f_2'(1-y^\star)} {\mu_1f_1(y^\star)+\mu_2f_2(1-y^\star)},$$

and let the quantities $\rho _\mu ^\star$ and $\sigma ^2$ be as follows:

\begin{align*} \rho_\mu^\star& :=\frac{f_1'(\frac{\mu^{21}}{\mu_2})(\frac{\mu^{11}\mu_2-\mu^{21}\mu_1}{\mu_2})+ f_2'(1-\frac{\mu^{11}}{\mu_1})(\frac{\mu^{11}\mu_2-\mu^{21}\mu_1}{\mu_1})} {\mu_1f_1(\frac{\mu^{12}}{\mu_2})+\mu_2f_2(1-\frac{\mu^{11}}{\mu_1})},\\ \sigma^2& :=\frac{((\mu^{11}-y^\star \mu_1)-(\mu^{21}-y^\star \mu_2))^2f_1(y^\star)f_2(1-y^\star)} {(\mu_1f_1(y^\star)+\mu_2f_2(1-y^\star))^2}. \end{align*}

Then under assumptions (A1)–(A3), the process $(Z_n)_{n\geq 0}$ introduced in (9), satisfies the following:

  1. 1. Suppose that ${\mu ^{11}}/{\mu _1} \leq {\mu ^{21}}/{\mu _2}$, then we have

    1. (a' 1) If both $f_1$ and $f_2$ are increasing then, $\sqrt {n}(Z_n-y^\star ) \overset {\mathscr {D}}{\longrightarrow } \mathscr {N}(0,{\sigma ^2}/{(2\hat {\gamma }-1)})$.

    2. (b' 1) If both $f_1$ and $f_2$ are decreasing and concave then,

      $$\sqrt{n}(Z_n-y^\star)\overset{\mathscr{D}}{\longrightarrow} \mathscr{N}\left(0,\frac{\sigma^2}{2\hat{\gamma}-1}\right)\quad \text{as soon as}\ \rho_\mu^\star{\lt}\tfrac{1}{2}.$$

  2. 2. If ${\mu ^{11}}/{\mu _1} \gt {\mu ^{21}}/{\mu _2}$, then we have

    1. (a' 2) If both $f_1$ and $f_2$ are decreasing then, $\sqrt {n}(Z_n-y^\star ) \overset {\mathscr {D}}{\longrightarrow } \mathscr {N}(0,{\sigma ^2}/{(2\hat {\gamma }-1)})$.

    2. (b' 2) If both $f_1$ and $f_2$ are increasing and concave then,

      $$\sqrt{n}(Z_n-y^\star)\overset{\mathscr{D}}{\longrightarrow} \mathscr{N}\left(0,\frac{\sigma^2}{2\hat{\gamma}-1}\right)\quad \text{as soon as}\; \rho_\mu^\star{\lt}\tfrac{1}{2}.$$

Proof. Notice that, Theorem 2.2 states that $Z_n\overset {{\rm a.s.}}{\longrightarrow } y^\star$. Now, we check the assumptions of the Theorem 2.1.

Recall that

$$Z_{n+1}=Z_n+\frac{1}{T_{n+1}}(h(Z_n)+\Delta M_{n+1}).$$

The function $h$ can be written as follows using the linear approximation

$$h(Z_n):=(Z_n-y^\star)g(Z_n),$$

where $g$ is a continuous function such that

(22)\begin{equation} g(Z_n)\overset{{\rm a.s.}}{\longrightarrow} h'(y^\star) \quad \text{as} \ n\rightarrow \infty. \end{equation}

Then, we have

\begin{align*} Z_{n+1}-y^\star& = Z_n-y^\star{+}\frac{1}{T_{n+1}}((Z_n-y^\star)g(Z_n))+\frac{\Delta M_{n+1}}{T_{n+1}}\\ & =\left(1-\frac{\hat{\gamma}_{n+1}}{n+1}\right)(Z_n-y^\star)+\frac{U_{n+1}}{n+1}, \end{align*}

so that

$$Q_{n+1}=\left(1-\frac{\hat{\gamma}_{n+1}}{n+1}\right)Q_n+\frac{U_{n+1}}{n+1},$$

where

$$Q_n:=Z_n-y^\star,\quad \hat{\gamma}_{n}:=\frac{-n}{T_n}g(Z_{n-1})= \frac{n}{T_n}\frac{-h(Z_{n-1})}{Z_{n-1}-y^\star}, \quad U_n:=n\frac{1}{T_n}\Delta M_n.$$

So on one hand, by (14) we have,

$$\frac{n}{T_n}\overset{{\rm a.s.}}{\longrightarrow} \frac{f_1(y^\star)+f_2(1-y^\star)}{\mu_1f_1(y^\star)+\mu_2f_2(1-y^\star)} \quad \text{as} \quad n\rightarrow \infty,$$

and by (22)

$$\frac{h(Z_{n-1})}{Z_{n-1}-y^\star}\overset{{\rm a.s.}}{\longrightarrow} h'(y^\star)\quad \text{as} \ n\rightarrow \infty.$$

Hence

$$\hat{\gamma}_n\overset{{\rm a.s.}}{\longrightarrow}\hat\gamma:=\frac{(\mu^{21}-y^\star \mu_2)f_2'(1-y^\star)- (\mu^{11}-y^\star \mu_1)f_1'(y^\star)}{\mu_1f_1(y^\star)+\mu_2f_2(1-y^\star)}+1 \quad \text{as} \ n\rightarrow \infty.$$

Thus the following hold:

  1. 1. Suppose that ${\mu ^{11}}/{\mu _1} \leq {\mu ^{21}}/{\mu _2}$.

    • If both $f_1$ and $f_2$ are increasing, we have

      $$(\mu^{21}-y \mu_2)f_2'(1-y)-(\mu^{11}-y \mu_1)f_1'(y)\gt0, \quad \forall y\in[\tfrac{\mu^{11}}{\mu_1}, \tfrac{\mu^{21}}{\mu_2}].$$
    • If both $f_1$ and $f_2$ are decreasing and concave, the fact that $\rho ^\star \leq \rho _\mu$ seals the proof.

  2. 2. Now suppose that ${\mu ^{11}}/{\mu _1}\gt{\mu ^{21}}/{\mu _2}$. Both cases $(a_3)$ and $(b_3)$ can be proven the same way as $(a_2)$ and $(b_2)$. On the other hand, we have

    $$\mathbb{E}((\Delta M_{n+1})^2\,|\,\mathscr{F}_{n})=\mathbb{E}(L_{n+1}^2\,|\,\mathscr{F}_{n})- \mathbb{E}(L_{n+1}\,|\,\mathscr{F}_{n})^2.$$
    Recall that
    $$L_{n+1}=(\xi_{n+1}^{11}-\xi_{n+1}^1Z_n){\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_1\}} +(\xi_{n+1}^{21}-\xi_{n+1}^2Z_n){\mathbb{1}}_{\{\textbf{X}_{n+1}=\textbf{e}_2\}}.$$
    We then get
    \begin{align*} \mathbb{E}(L_{n+1}^2\,|\,\mathscr{F}_{n})= \frac{(\mu^{11}-\mu_1Z_n)^2 f_1(Z_n)+(\mu^{21}-\mu_2Z_n)^2f_2(1-Z_n)}{f_1(Z_n)+f_2(1-Z_n)},\\ \mathbb{E}(L_{n+1}\,|\,\mathscr{F}_{n})^2= \frac{((\mu^{11}-\mu_1Z_n)f_1(Z_n)+(\mu^{21}-\mu_2Z_n)f_2(1-Z_n))^2}{(f_1(Z_n)+f_2(1-Z_n))^2}. \end{align*}
    Therefore,
    $$\mathbb{E}(L_{n+1}^2\,|\,\mathscr{F}_{n})-\mathbb{E}(L_{n+1}\,|\,\mathscr{F}_{n})^2= \frac{[(\mu^{11}-\mu_1Z_n)-(\mu^{21}-\mu_2Z_n)]^2f_1(Z_n)f_2(1-Z_n)}{( f_1(Z_n)+f_2(1-Z_n))^2}.$$
    Finally, we get
    \begin{align*} & \mathbb{E}\left(\left.\left(\frac{n}{T_n}\Delta M_n\right)^2\right|\mathscr{F}_{n-1}\right)\overset{{\rm a.s.}}{\longrightarrow} \frac{[(\mu^{11}-\mu_1y^\star)-(\mu^{21}-\mu_2y^\star)]^2f_1(y^\star)f_2(1-y^\star)} {(\mu_1f(y^\star)+\mu_2f_2(1-y^\star))^2} :=\sigma^2 \quad \text{as} \ n\rightarrow \infty. \end{align*}

Example 3.3. We consider once more the following replacement matrix

$$\Sigma:=\begin{pmatrix} 0 & a \\ b & 0 \end{pmatrix},$$

where $a,b\geq 0$ and $a\neq b$. Since $\mu ^{11}=\mu ^{22}=0$, $\mu ^{21}=a$ and $\mu ^{12}=b$, we have ${\mu ^{11}}/{\mu _1} \leq {\mu ^{21}}/{\mu _2}$. Moreover, suppose that $f_1\equiv f_2\equiv id_{[0.1]}$, then assertion $(a'_1)$ of Theorem 3.1 is satisfied. Hence,

$$\sqrt{n}(Z_n-y^\star) \overset{\mathscr{D}}{\longrightarrow} \mathscr{N}\left(0,\frac{\sqrt{a b}}{3(\sqrt{a}+\sqrt{b})^2}\right),$$

which meets the result in [Reference Aguech, Lasmar and Selmi2].

Conflict of interest

The author confirms that there is no conflict of interest.

References

Aguech, R. & Selmi, O. (2019). Unbalanced multi-drawing urn with random addition matrix. Arab Journal of Mathematical Sciences 26(1/2): 5774.CrossRefGoogle Scholar
Aguech, R., Lasmar, N., & Selmi, O. (2019). A generalized urn with multiple drawing and random addition. Annals of the Institute of Statistical Mathematics 71: 389408.Google Scholar
Bagchi, A. & Pal, A.K. (1985). Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures. Siam Journal on Algebraic and Discrete Methods 6(3): 394405.10.1137/0606041CrossRefGoogle Scholar
Bai, Z.-D. & Hu, F. (1999). Asymptotic theorems for urn models with nonhomogeneous generating matrices. Stochastic Processes and their Applications 80(1): 87101.10.1016/S0304-4149(98)00094-5CrossRefGoogle Scholar
Bai, Z.-D., Hu, F., & Shen, L. (2002). An adaptive design for multi-arm clinical trials. Journal of Multivariate Analysis 81(1): 118.10.1006/jmva.2001.1987CrossRefGoogle Scholar
Chauvin, B., Mailler, C., & Pouyanne, N. (2015). Smoothing equations for large Pólya urns. Journal of Theoretical Probability 28(3): 923957.CrossRefGoogle Scholar
Chen, M.R. & Kuba, M. (2013). On generalized Pólya urn models. Journal of Applied Probability Theory 50(4): 11691186.CrossRefGoogle Scholar
Chen, M.R. & Wei, C.Z. (2005). A new urn model. Journal of Applied Probability 42(4): 964976.CrossRefGoogle Scholar
Eggenberger, F. & Pólya, G. (1923). Uber die Statistik verketer Vorgiinge. Journal of Applied Mathematics and Mechanics 3(1): 279289.Google Scholar
Friedman, B. (1949). A simple urn model. Communications on Pure and Applied Mathematics 2(1): 5970.10.1002/cpa.3160020103CrossRefGoogle Scholar
González-Navarrete, M. & Lambert, R. (2019). Urn models with two types of strategies. Preprint arXiv:1708.06430.Google Scholar
Idriss, S. (2021). Nonlinear unbalanced urn models via stochastic approximation. Methodology and Computing in Applied Probability: 15737713, doi:10.1007/s11009-021-09858-6Google Scholar
Janson, S. (2006). Limit theorems for triangular urn schemes. Probability Theory and Related Fields 134(3): 417452.10.1007/s00440-005-0442-7CrossRefGoogle Scholar
Janson, S. (2020). Mean and variance of balanced Pólya urns. Advances in Applied Probability 52(4): 12241248.10.1017/apr.2020.38CrossRefGoogle Scholar
Janson, S. (2021). Functional limit theorem for multitype branching processes and generalized Pólya urns. Stochastic Processes and their Applications 110: 177245.CrossRefGoogle Scholar
Kuba, M. & Mahmoud, H. (2017). Two-color balanced affine urn models with multiple drawings. Advances in Applied Mathematics 90: 126, doi:10.1016/j.aam.2017.04.004CrossRefGoogle Scholar
Laruelle, S. & Pagès, G. (2013). Randomized urn models revisited using stochastic approximation. The Annals of Applied Probability 23(4): 14091436.CrossRefGoogle Scholar
Laruelle, S. & Pagès, G. (2019). Nonlinear randomized urn models: a stochastic approximation viewpoint. Electronic Journal of Probabiity 24: 147.Google Scholar
Lasmar, N., Mailler, C., & Selmi, O. (2018). Multiple drawing multi-colour urns by stochastic approximation. Journal of Applied Probability 55(1): 254281.CrossRefGoogle Scholar
Mahmoud, H. (2008). Pólya urn models. Orlando: Chapman-Hall.10.1201/9781420059847CrossRefGoogle Scholar
Mahmoud, H. (2021). Covariances in Pólya urn schemes. Probability in the Engineering and Informational Sciences: 112. doi:10.1017/S0269964821000450Google Scholar
Renlund, H. (2010). Generalized Pólya urns via stochastic approximation. Preprint arXiv:1002.3716v1.Google Scholar
Renlund, H. (2011). Limit theorem for stochastic approximation algorithm. Preprint arXiv:1102.4741v1.Google Scholar
Robbins, H. & Monro, S. (1951). A stochastic approximation method. Annals of Mathematical Statistics 22: 400407.10.1214/aoms/1177729586CrossRefGoogle Scholar
Smythe, R. (1996). Central limit theorems for urn models. Stochastic Processes and Their Applications 65: 115137.CrossRefGoogle Scholar
Figure 0

FIGURE 1. Examples of the function $h$.