Multiple drawing multi-colour urns by stochastic approximation

Nabil Lasmar, Cecile Mailler, Olfa Selmi

Research output: Contribution to journalArticle

1 Citation (Scopus)
22 Downloads (Pure)

Abstract

A classical P\'olya urn scheme is a Markov process whose evolution is encoded by a replacement matrix $(R_{i,j})_{1\leq i,j\leq d}$. At every discrete time-step, we draw a ball uniformly at random, denote its colour $c$, and replace it in the urn together with $R_{c,j}$ balls of colour $j$ (for all $1\leq j\leq d$).We study multi-drawing P\'olya urns, where the replacement rule depends on the random drawing of a set of $m$ balls from the urn (with or without replacement). Many particular examples of this situation have been studied in the literature, but the only general results are by Kuba \& Mahmoud (ArXiv:1503.09069 and 1509.09053).These authors prove second order asymptotic results in the $2$-colour case, under the so-called {\it balance} and {\it affinity} assumptions, the latter being somewhat artificial.The main idea of this work is to apply stochastic approximation methods to this problem, which enables us to prove analogous results to Kuba \& Mahmoud, but without the artificial {\it affinity} hypothesis, and, for the first time in the literature, in the $d$-colour case ($d\geq 3$). We also give some partial results in the two-colour non-balanced case, the novelty here being that the only results for this case currently in the literature are for particular examples.
Original languageEnglish
Pages (from-to)254-281
JournalJournal of Applied Probability
Volume55
Issue number1
DOIs
Publication statusPublished - 1 Mar 2018

Fingerprint

Stochastic Approximation
Replacement
Ball
Affine transformation
Second-order Asymptotics
Stochastic Methods
R-matrix
Approximation Methods
Markov Process
Discrete-time
Color
Drawing
Stochastic approximation
Denote
Partial

Cite this

Multiple drawing multi-colour urns by stochastic approximation. / Lasmar, Nabil; Mailler, Cecile; Selmi, Olfa.

In: Journal of Applied Probability, Vol. 55, No. 1, 01.03.2018, p. 254-281.

Research output: Contribution to journalArticle

Lasmar, Nabil ; Mailler, Cecile ; Selmi, Olfa. / Multiple drawing multi-colour urns by stochastic approximation. In: Journal of Applied Probability. 2018 ; Vol. 55, No. 1. pp. 254-281.
@article{88c08c74444d41f5a9a8fc520df3280b,
title = "Multiple drawing multi-colour urns by stochastic approximation",
abstract = "A classical P\'olya urn scheme is a Markov process whose evolution is encoded by a replacement matrix $(R_{i,j})_{1\leq i,j\leq d}$. At every discrete time-step, we draw a ball uniformly at random, denote its colour $c$, and replace it in the urn together with $R_{c,j}$ balls of colour $j$ (for all $1\leq j\leq d$).We study multi-drawing P\'olya urns, where the replacement rule depends on the random drawing of a set of $m$ balls from the urn (with or without replacement). Many particular examples of this situation have been studied in the literature, but the only general results are by Kuba \& Mahmoud (ArXiv:1503.09069 and 1509.09053).These authors prove second order asymptotic results in the $2$-colour case, under the so-called {\it balance} and {\it affinity} assumptions, the latter being somewhat artificial.The main idea of this work is to apply stochastic approximation methods to this problem, which enables us to prove analogous results to Kuba \& Mahmoud, but without the artificial {\it affinity} hypothesis, and, for the first time in the literature, in the $d$-colour case ($d\geq 3$). We also give some partial results in the two-colour non-balanced case, the novelty here being that the only results for this case currently in the literature are for particular examples.",
author = "Nabil Lasmar and Cecile Mailler and Olfa Selmi",
year = "2018",
month = "3",
day = "1",
doi = "10.1017/jpr.2018.16",
language = "English",
volume = "55",
pages = "254--281",
journal = "Journal of Applied Probability",
issn = "0021-9002",
publisher = "University of Sheffield",
number = "1",

}

TY - JOUR

T1 - Multiple drawing multi-colour urns by stochastic approximation

AU - Lasmar, Nabil

AU - Mailler, Cecile

AU - Selmi, Olfa

PY - 2018/3/1

Y1 - 2018/3/1

N2 - A classical P\'olya urn scheme is a Markov process whose evolution is encoded by a replacement matrix $(R_{i,j})_{1\leq i,j\leq d}$. At every discrete time-step, we draw a ball uniformly at random, denote its colour $c$, and replace it in the urn together with $R_{c,j}$ balls of colour $j$ (for all $1\leq j\leq d$).We study multi-drawing P\'olya urns, where the replacement rule depends on the random drawing of a set of $m$ balls from the urn (with or without replacement). Many particular examples of this situation have been studied in the literature, but the only general results are by Kuba \& Mahmoud (ArXiv:1503.09069 and 1509.09053).These authors prove second order asymptotic results in the $2$-colour case, under the so-called {\it balance} and {\it affinity} assumptions, the latter being somewhat artificial.The main idea of this work is to apply stochastic approximation methods to this problem, which enables us to prove analogous results to Kuba \& Mahmoud, but without the artificial {\it affinity} hypothesis, and, for the first time in the literature, in the $d$-colour case ($d\geq 3$). We also give some partial results in the two-colour non-balanced case, the novelty here being that the only results for this case currently in the literature are for particular examples.

AB - A classical P\'olya urn scheme is a Markov process whose evolution is encoded by a replacement matrix $(R_{i,j})_{1\leq i,j\leq d}$. At every discrete time-step, we draw a ball uniformly at random, denote its colour $c$, and replace it in the urn together with $R_{c,j}$ balls of colour $j$ (for all $1\leq j\leq d$).We study multi-drawing P\'olya urns, where the replacement rule depends on the random drawing of a set of $m$ balls from the urn (with or without replacement). Many particular examples of this situation have been studied in the literature, but the only general results are by Kuba \& Mahmoud (ArXiv:1503.09069 and 1509.09053).These authors prove second order asymptotic results in the $2$-colour case, under the so-called {\it balance} and {\it affinity} assumptions, the latter being somewhat artificial.The main idea of this work is to apply stochastic approximation methods to this problem, which enables us to prove analogous results to Kuba \& Mahmoud, but without the artificial {\it affinity} hypothesis, and, for the first time in the literature, in the $d$-colour case ($d\geq 3$). We also give some partial results in the two-colour non-balanced case, the novelty here being that the only results for this case currently in the literature are for particular examples.

U2 - 10.1017/jpr.2018.16

DO - 10.1017/jpr.2018.16

M3 - Article

VL - 55

SP - 254

EP - 281

JO - Journal of Applied Probability

JF - Journal of Applied Probability

SN - 0021-9002

IS - 1

ER -