Multiple drawing multi-colour urns by stochastic approximation

Nabil Lasmar, Cecile Mailler, Olfa Selmi

Research output: Contribution to journalArticle

2 Citations (Scopus)
24 Downloads (Pure)

Abstract

A classical Pólya urn scheme is a Markov process where the evolution is encoded by a replacement matrix (Ri, j)1 ≤ i, j ≤ 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 Rc, j balls of colour j (for all 1 ≤ j ≤ d). We study multiple drawing Pólya 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 due to Kuba and Mahmoud (2017). These authors proved second-order asymptotic results in the two-colour case, under the so-called balance and 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 and Mahmoud, but without the artificial affinity hypothesis, and, for the first time in the literature, in the d-colour case (d ≥ 3). We also provide some partial results in the two-colour nonbalanced 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
Number of pages28
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

Keywords

  • Multiple drawing Pólya urn
  • discrete-time martingale
  • limit theorem
  • reinforced process
  • stochastic approximation

ASJC Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Statistics, Probability and Uncertainty

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{\'o}lya urn scheme is a Markov process where the evolution is encoded by a replacement matrix (Ri, j)1 ≤ i, j ≤ 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 Rc, j balls of colour j (for all 1 ≤ j ≤ d). We study multiple drawing P{\'o}lya 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 due to Kuba and Mahmoud (2017). These authors proved second-order asymptotic results in the two-colour case, under the so-called balance and 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 and Mahmoud, but without the artificial affinity hypothesis, and, for the first time in the literature, in the d-colour case (d ≥ 3). We also provide some partial results in the two-colour nonbalanced case, the novelty here being that the only results for this case currently in the literature are for particular examples.",
keywords = "Multiple drawing P{\'o}lya urn, discrete-time martingale, limit theorem, reinforced process, stochastic approximation",
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ólya urn scheme is a Markov process where the evolution is encoded by a replacement matrix (Ri, j)1 ≤ i, j ≤ 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 Rc, j balls of colour j (for all 1 ≤ j ≤ d). We study multiple drawing Pólya 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 due to Kuba and Mahmoud (2017). These authors proved second-order asymptotic results in the two-colour case, under the so-called balance and 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 and Mahmoud, but without the artificial affinity hypothesis, and, for the first time in the literature, in the d-colour case (d ≥ 3). We also provide some partial results in the two-colour nonbalanced case, the novelty here being that the only results for this case currently in the literature are for particular examples.

AB - A classical Pólya urn scheme is a Markov process where the evolution is encoded by a replacement matrix (Ri, j)1 ≤ i, j ≤ 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 Rc, j balls of colour j (for all 1 ≤ j ≤ d). We study multiple drawing Pólya 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 due to Kuba and Mahmoud (2017). These authors proved second-order asymptotic results in the two-colour case, under the so-called balance and 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 and Mahmoud, but without the artificial affinity hypothesis, and, for the first time in the literature, in the d-colour case (d ≥ 3). We also provide some partial results in the two-colour nonbalanced case, the novelty here being that the only results for this case currently in the literature are for particular examples.

KW - Multiple drawing Pólya urn

KW - discrete-time martingale

KW - limit theorem

KW - reinforced process

KW - stochastic approximation

UR - http://www.scopus.com/inward/record.url?scp=85044612786&partnerID=8YFLogxK

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 -