1. Introduction
Urn models, as classic examples of stochastic processes with reinforcement, can be used to describe the underlying mathematical mechanisms in various evolutionary processes in fields such as epidemiology, networks, economics, and physics. The classic urn models deal with urns containing balls of two colors, and at each discrete step, one ball is sampled and reinserted, and balls are added into the urn based on the observed color. The asymptotic composition for this type of urn processes is well studied and a comprehensive overview can be found in [Reference Mahmoud15]. Many directions of generalizations have been developed, including considering urns with more than two colors (e.g., [Reference Gouet8,Reference Janson9,Reference Lasmar, Mailler and Selmi14]), allowing deleting balls (e.g., [Reference Flajolet and Huillet6,Reference Kingman and Volkov10,Reference Kuba and Panholzer12]), taking samples of size $s\geq 1$ at each step (e.g., [Reference Kuba and Mahmoud11,Reference Kuba, Mahmoud and Panholzer13,Reference Lasmar, Mailler and Selmi14]), and allowing the replacement rules to be time-dependent and random (e.g., [Reference Chen2,Reference Crimaldi, Louis and Minelli3,Reference Feng and Mahmoud5,Reference Pemantle16]).
A time-dependent version of Pólya urn was proposed in [Reference Pemantle16]. In a classic Pólya urn, the urn process initially starts with $W_0$ white and $B_0$ blue balls. At each discrete time unit, one ball is sampled and put back, and an integer number $c \gt 0$ balls are reinforced for the same color as the drawn sample. It is known in [Reference Eggenberger and Pólya4] that the proportion of white balls converges almost surely to beta distribution with parameters ${W_0}/{c}$ and ${B_0}/{c}$. A time-dependent generalization is studied in [Reference Pemantle16], where $c$ is replaced by a dynamic function $F(n)$. Necessary and sufficient conditions on the sequence $\{F(n)\}$ are given for the proportion of white balls to converge to a Bernoulli distribution with parameter ${W_0}/{(W_0+B_0)}$. The condition for the limit distribution to have atoms and the locations of the atoms have also been discussed. The Bernoulli limit has also been obtained via a distributional equation in [Reference Feng and Mahmoud5]. For this two-color single-drawing time-dependent Pólya urn process, a study on conditions for domination and monopoly can be found in [Reference Sidorova19]. A generalization to multiple-drawing Pólya-type urns is considered in [Reference Chen2].
In this study, we consider an analogue of the class dealt with in Chen [Reference Chen2] and Pemantle [Reference Pemantle16] to a class of multiple-drawing Friedman-type urns. We start with a two-color (say white and blue) multiple-drawing urn and sample $s\geq 1$ balls at each discrete unit of time. We assume that the samples are taken with replacement. The results under sampling without replacement can be obtained through a similar manner. At each step, we examine the composition of the sample, reinsert the drawn balls into the urn and execute the replacement matrix. We specify a class of multiple-drawing dynamic Friedman urn with opposite-reinforcement by assuming that the replacement matrix has the symmetric reinforcement feature of a classic Friedman urn and the replacement matrix is changing over time. While keeping the urn to be balanced, we allow the replacement entries to be random variables (with some restriction for large-increment regime), so the symmetric reinforcement is in the mean sense. We further define that the class is opposite-reinforcing in the mean sense by assuming the color with lower appearance in the sample gets supported stronger in the mean sense. A special case of this class with a fixed replacement matrix that is constant over time has been studied in [Reference Kuba, Mahmoud and Panholzer13]. In their study, a sample of size $s$ is taken at each step, and for every white ball in the sample, a positive integer $C$ blue balls are added, and vice versa. In the class studied in [Reference Kuba, Mahmoud and Panholzer13], the reinforcement is opposite and affine in the sense that the lower the appearance of a color, the stronger that color gets reinforced, and the number of increments of each color is a multiple of the number of that color in the drawn sample. Later, we see that affinity is a condition we need if we seek a martingale theory-based proof of convergence. Another special case with a random replacement matrix where the distributions of the replacement entries stay constant over time can be found in [Reference Gao and Mahmoud7].
For the class we consider, we assume the urn to be balanced with balance factor $Kf(n)$, for integer $K \gt 0$, and for some positive function $f(n)\ge 1$ nondecreasing in $n$, and the total addition is separated into white and blue based on the composition of the sample and an extra layer of randomness from a random variable on the interval $[0,K)$. The addition rules are represented by a replacement matrix, the rows of which are indexed by the composition of the sample, and the columns are indexed by the colors in the scheme, namely white and blue. We consider a matrix representation where the $i$th row is the number of white and blue balls (respectively) that are added to the urn when the sample contains $i-1$ blue balls. For a multiple-drawing dynamic Friedman urn with opposite-reinforcement, the replacement matrix is given by
for integer $K \gt 0$, and for some positive function $f(n)\ge 1$ nondecreasing in $n$, where ${X_{n,i}}'s$ are distributed as independent random variables on the support $[0,K)$, for $0\leq i\leq s$. Since we are focusing on opposite-reinforcement schemes, we exclude Pólya-type schemes by keeping out $K$ in the admissible support to avoid the realization that all ${X_{n,i}}'s$ in the upper half of the replacement matrix are equal to $K$ (this class is studied in [Reference Chen2]). Let $\mathbb {F}_n$ be the sigma field generated by the first $n$ draws, we assume $X_{n,i}$ and the $n$th round of drawing are conditionally independent, given $\mathbb {F}_{n-1}$, for all $i$, and ${X_{n,i}}'s$ are independent and identically distributed as $\{X_0,X_1,X_2,\,\ldots, X_s\}$ for all $n$. As discussed in [Reference Bandyopadhyay and Thacker1], the replacement entries can be scaled and the same results hold, so we do not have integer value assumptions on $f(n)$ and $X_{n,i}$. Proper scaling can be found for the process to make sense in terms of balls and urns. For the proposed class, we require
where $\varphi (i)+\varphi (s-i)=K$, for each $0\leq i\leq s$, and $\varphi (i)\leq {K}/{2}$, for $0\leq i\leq \lfloor {s}/{2}\rfloor.$ We exclude the uninteresting process where $\varphi (i)={K}/{2}$ for all $i$, so that there is at least some $0\leq i\leq \lfloor {s}/{2}\rfloor$, such that $\varphi (i) \lt {K}/{2}$. The condition $\varphi (i)+\varphi (s-i)=K$ ensures that the addition is symmetric in the mean sense. By the condition $\varphi (i)+\varphi (s-i)=K$, we see that if $s$ is even and a tie appears in the sample, we have $\varphi ({s}/{2})={K}/{2}$.
In the case $K=s$ and $\varphi (i)=i$, for each $0\leq i\leq s$, we can set $X_i=\varphi (i)$ and have a sequences of deterministic replacement matrices given by
which is an extension to the class considered in [Reference Kuba, Mahmoud and Panholzer13], when $C$ is replaced by $f(n)$.
An example for random addition is given by
for $X_{n,i}=(s-i)-(s-2i)B_n(p)$, where ${B_n(p)}$'s are distributed as independent $\operatorname {\textrm {Bernoulli}}(p)$ random variables, for $\frac {1}{2} \lt p \lt 1$. We see that in the single-drawing case, the replacement matrix reduces to
for $\frac {1}{2} \lt p \lt 1$.
Let $W_n$ and $B_n$ be respectively the number of white and blue balls in the urn after $n$ draws. We assume $W_0 \gt s$ and $B_0 \gt s$ to ensure tenability. Let $T_n$ be the total number of balls in the urn after $n$ draws. We have $T_n=W_n+B_n=T_0+\sum _{i=1}^{n}Kf(i)$. Since the total $T_n$ is deterministic, the study of one color implies the results of the other. So our objective is to study the asymptotic behavior of the proportion of white balls, which we define as $Q_n={W_n}/{T_n}$.
2. Classification
After some initial analysis, we find that the asymptotic behavior of $Q_n$ can be characterized by
Along this line of discussion, we study the following regimes:
(1) $\lim _{n\to \infty } {(nK f(n))}/{T_n}=\alpha$, for some positive real constant $a$.
(2) $\lim _{n\to \infty } {(Kf(n))}/{T_n}=\beta$, for $\beta \in (0,1)$.
(3) $\lim _{n\to \infty } {(Kf(n))}/{T_n}=1$.
Remark 2.1. Regime (1) does not cover the entire spectrum, in which $\lim _{n\to \infty } {(Kf(n))}/{T_n}=0$. Since we rely on stochastic approximation to obtain the limit theorems for urns in this regime, the rate in regime (1) is required. We shall work on the remaining spectrum in the future.
Example 2.1. For $f(n)=a n^b+c$, for nonnegative real constants $a$, $b$, and $c$, we have
since $T_n\sim K\int _{x=0}^{n}ax^b\,dx=({Ka}/{(b+1)})n^{b+1}$.
Example 2.2. For $f(n)=a^n+c$, for nonnegative real constant $c$ and real constant $a \gt 1$, we have
Example 2.3. For $f(n)=a^{a^n}+c$, for nonnegative real constant $c$ and real constant $a \gt 1$, we have
In view of the growth rate of the total $T_n$ for the three regimes, we observe that conditions (1)–(3) can be interpreted as a relation between the increment and the total $T_n$:
(1) $\lim _{n\to \infty } {(nK f(n))}/{T_n}=\alpha$ implies $f(n)=o(T_{n-1})$,Footnote 1 which we identify as small-increment urns.
(2) $\lim _{n\to \infty } {(Kf(n))}/{T_n}=\beta$, for $\beta \in (0,1)$, implies $f(n)=\Theta (T_{n-1})$,Footnote 2 which we identify as large-increment urns.
(3) $\lim _{n\to \infty } {(Kf(n))}/{T_n}=1$ implies $f(n)=\omega (T_{n-1})$,Footnote 3 which we also classify as large-increment urns.
After some preliminary analysis, we find that the small-increment regime and the large-increment regime have different asymptotic behaviors. We study the small-increment regime using the method of stochastic approximation and the large-increment regime using the convergence of supermartingales. The combination of these two methods reveals the dynamics of the urn composition as the rate of the function $f(n)$ increases.
3. Small-increment urns
It is easy to verify that a scheme with a constant, logarithmic, linear, or polynomial $f(n)$ with any positive integer initial composition to start the first draw and some $s\geq 1$ is in the class of small-increment urns. For example, the classic Friedman urn with replacement matrix $\left (\begin {smallmatrix} 0 & c\\ c & 0 \end {smallmatrix}\right )$ has $\alpha =1$.
3.1. Model assumptions
For an urn scheme to fall in the class of small-increment dynamic Friedman urns with opposite-reinforcement, we require the following assumptions on the replacement rules:
3.2. Stochastic approximation algorithm
We first show that in a small-increment dynamic Friedman urn, the proportion of white balls satisfies a stochastic approximation algorithm, and then we apply the limit theorems for the stochastic approximation algorithms. We start by introducing the definition of stochastic approximation.
Definition 3.1. (Stochastic approximation algorithm)
A stochastic approximation algorithm $\{Q_n\}_{n\geq 0}$ is a stochastic process taking values in $[0,1]$, adapted to the filtration {$\mathbb {F}_n$}, that satisfies
where $\gamma _n, U_n$ are random variables measurable in $\mathbb {F}_n$, $h:[0,1]\rightarrow \mathbb {R}$ and the following conditions hold almost surely:
for $n\geq 1$, and for positive real constants $c_\ell, c_h, c_f, c_u$, and $c_e$.
Proposition 3.1. For a small-increment dynamic Friedman urn with $\lim _{n\to \infty } {(nK f(n))}/{T_n}=\alpha$, for some positive real constant $\alpha$, the proportion of white balls $Q_n$ satisfies a stochastic approximation algorithm.
Proof. We have
where $\mathbb {I}_{n}^{(i)}$ is the indicator that there are $i$ blue balls in the $n$th sample drawn from the urn, and $\gamma _n={f(n)}/{T_n}$. Let us define $h(Q_{n-1}) = {\mathbb {E}}[{M}_{n} \, \vert \, \mathbb {F}_{n-1}]$, hence, we get $U_{n} = M_{n}-h(Q_{n-1})$. With this setup, we check the conditions of a stochastic approximation algorithm:
(i) For small-increment urn schemes, we have $\lim _{n\to \infty } {(n Kf(n))}/{T_n}=\alpha$, so for every $\epsilon \gt 0$, there exists some $N_0$, such that for every $n \gt N_0$, we have ${(\alpha -\epsilon )}/{n} \le {Kf(n)}/{T_n}\leq {(\alpha +\epsilon )}/{n}$. For $j\leq N_0$, set $H=\max ({jf(j)}/{T_j})$ and $L=\min ({jf(j)}/{T_j})$. We then define $c_h=\max (H,{(\alpha +\epsilon )}/{K})$ and $c_\ell =\min (L,{(\alpha -\epsilon )}/{K})$, then we have ${c_\ell }/{n} \le {f(n)}/{T_n}\leq {c_h}/{n}$.
(ii) For $h(Q_{n-1})$, we get
\begin{align*} h(Q_{n-1})& ={\mathbb{E}}[M_{n} \, \vert \, \mathbb{F}_{n-1}] \\ & ={-}KQ_{n-1} + \sum_{i=0}^{s} {\mathbb{E}}[X_{n,i}\, \vert \, \mathbb{F}_{n-1}] \,{\mathbb{E}}[\mathbb{I}_{n}^{(i)}\, \vert \, \mathbb{F}_{n-1}]\\ & ={-}KQ_{n-1}+\sum_{i=0}^{s}\varphi(i){s \choose i}Q_{n-1}^{s-i} (1-Q_{n-1})^i. \end{align*}Thus, we have$$|h(Q_{n-1})| = |{\mathbb{E}}[M_{n} \, \vert \, \mathbb{F}_{n-1}] | \le 2K =: c_f.$$(iii) $|U_n|$ is also uniformly bounded, since we have
$$|U_n|\leq |M_{n}| + |h(Q_{n-1})| \leq 2K+ c_f=: c_u.$$(iv) The urn is balanced with balance factor $Kf(n)$, leading to
$$|{\mathbb{E}}[\gamma_{n}U_{n} \, \vert \, \mathbb{F}_{n-1}]| = \left|\frac{f(n)}{T_n} {\mathbb{E}}[M_{n} - {\mathbb{E}}({M}_{n} \, \vert \, \mathbb{F}_{n-1})\, \vert \, \mathbb{F}_{n-1}) ]\right| = 0 =: c_e.$$
3.3. Limit theorems
Since we have verified that $\{Q_n\}_{n\geq 0}$ is a stochastic approximation algorithm, we can apply the limit theorems of stochastic approximation. The almost-sure convergence of a stochastic approximation algorithm is guaranteed when the process has a unique stable point.
Definition 3.2. We call $r \in S_f= \{x:h(x)=0\}$ a stable point, if $h(x)(x-r) \lt 0$, whenever $x\not = r$ and $x$ is close enough to $r$ (in the sense of the existence of a neighborhood). For a Lipschitz function $h$, this is equivalent to $h'(r) \lt 0$.
We apply the limit theorems in [Reference Renlund17,Reference Renlund18], which we state below.
Theorem 3.1. (Renlund [Reference Renlund17])
If $f$ is continuous, then $\lim _{n\rightarrow \infty } Q_n$ exists almost surely, and is in $S_f$. If $p$ is a stable point, then we have $\mathbb {P} (\lim _{n \to \infty }Q_n = p) \gt 0$.
Theorem 3.2. (Renlund [Reference Renlund18])
The asymptotic behavior of the sequence $\{Q_n\}_{n\geq 0}$ depends on the value of $\hat {\gamma }=\lim _{n\to \infty }\hat {\gamma _n}$. If the function $h(x)$ is Lipschitz, then $\lim _{n\to \infty }\hat {\gamma _n}=-h'(r)\lim _{n\to \infty }n\gamma _n$. If $\hat {\gamma } \gt \frac {1}{2}$ and $\sigma ^2 \gt 0$, then
where $\sigma ^2 = \lim _{n\to \infty } {\mathbb {E}}[\hat U_{n}^2 \, \vert \, \mathbb {F}_{n-1}]$ ($\hat U_n =n\gamma _nU_n$), and $Q^*$ is the almost-sure limit in Theorem 3.1.
By Theorem 3.1, we have the following proposition for schemes in the small-increment regime.
Proposition 3.2. For a small-increment dynamic Friedman urn with $\lim _{n\to \infty } {(n Kf(n))}/{T_n}=\alpha$, for some positive real constant $\alpha$, the proportion of white balls $Q_n$ converges almost surely to $\frac {1}{2}$.
Proof. The function $h$ is defined by, $\forall \,x\in [0,\,1]$,
For all $x\in [0,\,1],$ we have $h(1-x)=-h(x)$, since
In particular, we conclude that $h(\frac {1}{2})=0$. And for all $x \gt \frac {1}{2}$, we have
By a similar argument, we can verify that $h(x) \gt 0$, for $x \lt \frac {1}{2}$. So the only zero of $h$ in $[0,\,1]$ is $\frac {1}{2}$.
We further have that
so that
Then, we can write
and we conclude that $h'(\frac {1}{2}) \lt 0$ is guaranteed if we have $\varphi (i)\leq {K}/{2}$, for $0\leq i\leq \lfloor {s}/{2}\rfloor$, which is the class of opposite-reinforcing matrices. Since $\frac {1}{2}$ is the unique zero and the derivative of $h(x)$ at this point is negative, we verify that $\frac {1}{2}$ is a stable point and the process converges to it almost surely.
Remark 3.1. Since we have
to guarantee that $h'(\frac {1}{2}) \lt 0$, it suffices to have that $\forall i\leq {s}/{2}$,
with the strict inequality holding for at least one index. This condition, which specifies a class that is broader than the class of opposite-reinforcing matrices, is sufficient but not necessary. For example, we can have
with $f(n)=n$, and $p=\frac {1}{3}$. We get $\varphi (0)=\frac {2}{3}$ and $\varphi (1)=\frac {1}{3}$, so the matrix is self-reinforcing, but we can check that condition given by Eq. (3.1) holds, so the process $\{Q_n\}_{n\geq 0}$ converges to $\frac {1}{2}$ almost surely.
From the known results in stochastic approximation as in [Reference Renlund18] (Theorem 3.2), the asymptotic distribution of $\{Q_n\}_{n\geq 0}$ is characterized by an index $\hat {\gamma }$ which is defined as $\hat {\gamma }=\lim _{n\to \infty }\hat {\gamma _n}=-h'(r)\lim _{n\to \infty }n\gamma _n$, if the function $h(x)$ is Lipschitz. For the class of small-increment dynamic Friedman urn with opposite-reinforcement, we get
We know that by definition, we have $\alpha =\lim _{n\to \infty } {(n Kf(n))}/{T_n}$. Since we take $f(n)\ge 1$ and nondecreasing in $n$, the lowest rate of addition occurs when we apply a constant function $f(n)=c$, for some positive real constant $c$. Hence, for the class of small-increment urns, we have $1\leq \alpha \leq \hat {\gamma }.$
With this range of $\hat {\gamma }$, we have central limit theorems as from [Reference Renlund18] (Theorem 3.2). The variance of the asymptotic distribution includes a parameter defined as $\sigma ^2 = \lim _{n\to \infty } {\mathbb {E}}[\hat U_{n}^2 \, \vert \, \mathbb {F}_{n-1}]$, where $\hat U_n =n\gamma _nU_n$.
Proposition 3.3. For a dynamic Friedman small-increment urn with $\lim _{n\to \infty } {(n Kf(n))}/{T_n}=\alpha$, for some positive real constant $\alpha$, we have
where
and $\sigma ^2$ is given as in Eq. (3.2).
Proof. Define $p_{n,j}$ as the conditional probability that we get $j$ white balls in the $n$th sample given $\mathbb {F}_{n-1}$. By definition, we get the following for $\hat U_{n}$:
Then, we get
where $\mu _{2,i}$ is the second moment of $X_i$. The result follows by applying Theorem 3.2.
4. Large-increment urns
We used stochastic approximation to prove limit theorems for small-increment urns. Stochastic approximation is applicable for small-increment urns since the step-size is diminishing with respect to time. Namely, we have ${c_\ell }/{n} \le {f(n)}/{T_n}\leq {c_h}/{n}$. This rate of step-size is key to convergence of the stochastic approximation algorithm. For the large-increment urns, when formulated as a stochastic approximation algorithm, the step-size is of linear rate, and the convergence of the algorithm is not guaranteed.
Hence, we resort to the convergence of supermartingale for limit theorems. In order to build a supermartingale, we need the affinity condition to break the dependence on higher moments, so that the conditional expectation of $Q_n$ depends only on $Q_{n-1}$, not on $Q_{n-1}^m$, for $m \gt 1$. For this reason, we impose the affinity condition (Eqs. (4.1) and (4.2)) and consider a smaller class with fixed replacement entries for large-increment urns. The affinity condition is developed in [Reference Kuba and Mahmoud11]. It has been shown in [Reference Kuba and Mahmoud11] that for a balanced urn scheme with replacement matrix (sample size is $s$)
if the replacement entries satisfy
for $0\leq k\leq s$, then we have
for deterministic $\alpha _n$ and $\beta _n$. This condition essentially requires that for a given pair of $a_{s-1}$ and $a_s$, the rest of the entries of the first column of the replacement matrix have to be filled in such that the distance of every adjacent pair is the same as the distance between $a_{s-1}$ and $a_s$. Upon checking, we find that this relation holds when the matrix is multiplied by the dynamic function $f(n)$. For a dynamic urn with replacement matrix
the affinity condition given by Eq. (4.2) ensures that Eq. (4.3) holds. For a simpler representation, we take the balance factor to be $sf(n)$. The result can easily generalize to arbitrary balance factor $Kf(n)$. For a dynamic urn with balance factor $sf(n)$, the replacement matrix is given by
where $\frac {1}{2} \lt p\leq 1$. For each $0\leq i\leq s$, we have $a_i=ip+(s-i)(1-p)$. Compared with the class treated in Section 3, this is a subclass by requiring the replacement entries to satisfy the affinity condition and take fixed values. Shrinking to this subclass allows us to formulate a supermartingale. We summarize the model assumptions for the large-increment regime in the following subsection.
4.1. Model assumptions
For an urn scheme to fall in the class of large-increment dynamic Friedman urns with opposite-reinforcement, we require the following assumptions on the replacement rules:
(i) The replacement matrix is specified by Eq. (4.5), with $\frac {1}{2} \lt p\leq 1$.
(ii) The rate of the dynamic function $f(n)$ satisfies $\lim _{n\to \infty } {(K f(n))}/{T_n}=\beta$, for $\beta \in (0,1]$.
(iii) The sequence $\{{f(n)}/{T_n}\}$ is monotonically increasing.
Next, we formulate a supermartingale to prove almost-sure convergence of the proportion of white balls under the model assumptions.
4.2. Supermartingalization
The proof strategy is similar to the one used in Section 5.2 in [Reference Kuba and Mahmoud11]. Aiming at a simpler representation, we construct the random variable $\tilde {Q}_n=Q_n-\frac {1}{2}$. By the stochastic recurrence
where $\mathbb {I}_{n}^{(i)}$ is the indicator that there are $i$ blue balls in the $n$th sample, we have the following conditional expectation:
By Eq. (4.7), we have
Proposition 4.1. For the class of affine opposite-reinforcing dynamic Friedman urns with large-increment, we have that
is a supermartingale, if the sequence $\{{f(n)}/{T_n}\}$ is monotonically increasing.Footnote 4
Proof. Taking the square of Eq. (4.6), and with the result from Eq. (4.8), we verify that
The existence of such positive $c_0$ is guaranteed by having $\lim _{n\to \infty } {(sf(n))}/{T_n}=\beta$, for $\beta \in (0,1]$, and $\frac {1}{2} \lt p\leq 1$. Rearranging, we get, for some positive $c_1$, that
by assigning $c_1T_n/f(n)+c_0\leq c_1T_{n-1}/f(n-1)$. The existence of such $c_1$ is guaranteed when we have that the sequence $\{f(n)/T_n\}_n$ is monotonically increasing. Since we assume opposite-reinforcement, we have $\frac {1}{2} \lt p\leq 1$, hence, we get
For $\frac {1}{2} \lt p\leq 1$, we have
verifying $\tilde {Q}_n^2+ {c_1T_n}/{f(n)}$ is a positive supermartingale, thus converges almost surely by Williams [Reference Williams20]. This implies that $Q_n$ converges almost surely, to some limit $L$, by the continuous mapping theorem.
In next section, we will show a method to identify the almost-sure limit.
4.3. Limit theorems
The almost-sure limit can be obtained by a distributional equation, similar as in [Reference Feng and Mahmoud5]. For the single-drawing dynamic Pólya urn considered in [Reference Feng and Mahmoud5], the distributional equation can be solved explicitly to get the limit distribution, which is not always the case for multiple-drawing urns.
Theorem 4.1. For a large-increment affine opposite-reinforcing dynamic Friedman urn, we have
where $T$ is a random variable taking values in $\{0,1,\ldots, s\}$ and $a_i$ is the $i$th entry of the first column of the replacement matrix given by Eq. (4.5). The distribution of $T$ is given by ${\mathbb {P}}[T=i] =\lim _{n \to \infty }{\mathbb {P}}[\mathbb {I}_{n}^{(i)}=1],$ which satisfies Eq. (4.12),
Proof. We start with a distributional equation
where $\mathbb {I}_{n}^{(i)}$ is the indicator for the event that we have $i$ blue balls in $n$th sample. By the almost-sure convergence of $Q_n$, taking limit on both sides, we get
Given that $\lim _{n\to \infty } {(sf(n))}/{T_n}=\beta \in (0,1]$ and $Q_n\overset {{\rm a.s.}}{\longrightarrow } L$, we get
which is equivalent to
For each $i\in \{0, 1, 2,\ldots, s\}$, we have
where the exchange of limit and integration is justified by the dominated convergence theorem.
Next, we verify that the claimed distribution satisfies Eqs. (4.11) and (4.12), proving the stated result. Since we have shown that $Q_n$ converges almost surely in the previous section, there is a unique distribution that satisfies Eqs. (4.11) and (4.12). From Eq. (4.11), the limit of an indicator takes value in $\{0,1\}$. Hence, we have $L$ takes value in the set $S=\{1-p, (1-p)+{(2p-1)}/{s},\ldots, p\}$, which is the set formed by the entries of the first column of the replacement matrix divided by $s$. We have that $L$ is distributed on the set $S$ with the probabilities governed by Eq. (4.12), proving the stated result.
Remark 4.1. Using the following identities: for all real numbers $a$ and $b$,
and Eqs. (4.11) and (4.12), we deduce easily that,
Moreover, Eqs. (4.11) and (4.12) give recursively all the moment of $L$, and so characterize the distribution.
Remark 4.2. From Eq. (4.12), the distribution of $L$ can be identified by solving the following system: $\forall i\in \{0, 1,\ldots, s\}$, denote by $p_i:={\mathbb {P}}[L=1-p+({(2p-1)}/{s})i]$, and we have
We illustrate how to identify the limit $L$ using Eq. (4.12) by one single-drawing example and one multiple-drawing example.
Example 4.1. For the single-drawing dynamic classic Friedman urn with replacement matrix $f(n)\left (\begin {smallmatrix} 0 & 1\\ 1 & 0 \end {smallmatrix}\right )$, we have that the class of small-increment schemes have the following limit law:
For the class of large-increment schemes, we have
By Eq. (4.12), we get
It is easy to check that $T={\rm Bernoulli}(\frac {1}{2})$ satisfies Eqs. (4.13) and (4.14). We have $a_0=0$ and $a_1=1$, hence, the limit distribution is ${\rm Bernoulli}(\frac {1}{2})$.
Example 4.2. For the affine dynamic Friedman urn with replacement matrix
we have that the class of small-increment schemes have the following limit law:
For the class of large-increment schemes, we have
By Theorem 4.1, we have that $L$ is distributed on $S=\{\frac {1}{4}, \frac {1}{2}, \frac {3}{4}\}$, with probability $\{p_1,p_2,p_3\}$. From Remark 4.1, we have ${\mathbb {E}}[L]=\frac {1}{2}$. By the symmetry in the replacement matrix, we have $p_3=p_1=p$ and $p_2=1-2p$. Then, by Eq (4.12), we have
which yields $p=\frac {2}{7}$. Hence, we get $L$ is distributed on $S=\{\frac {1}{4}, \frac {1}{2}, \frac {3}{4}\}$, with probability $\{\frac {2}{7}, \frac {3}{7}, \frac {2}{7}\}$.
For both the class of single-drawing dynamic Pólya urns [Reference Pemantle16], and the class of multiple-drawing dynamic Pólya urns [Reference Chen2], the limit distribution of the proportion of white balls is a discrete random variable when the increment is large. For small-increment dynamic Pólya urns, it has been shown in [Reference Chen2] that the distribution of the proportion of white balls is absolutely continuous when $f(n)$ is bounded, but there is a regime between bounded-increment and large-increment that no conclusion has been made so far.
For the class of dynamic Friedman urns with multiple-drawing and opposite-reinforcement, we have a similar situation where we observe a change from continuous limit to discrete limit as we increase the rate of increment. For the class of dynamic Friedman urns with multiple-drawing and opposite-reinforcement, we are only able to treat the affine subclass for large-increment urns with fixed replacement entries. This is the remaining task we will continue further in our future work.
Acknowledgments
The authors are grateful to Hosam Mahmoud for various discussions on the scope of this research, and for many suggestions which helped improve the quality of this paper. The authors also thank the anonymous reviewers for many critical and helpful comments and suggestion, which helped us improve the exposition of the paper. The second author would like to extend his sincere appreciation to the Deanship of Scientific Research at King Saud University for funding their Research group No. (RG-1441-317).
Competing interests
The authors declare no conflict of interest.