Multiple drawing multi-colour urns by stochastic approximation

Nabil Lasmar, Cecile Mailler, Olfa Selmi

Research output: Contribution to journalArticlepeer-review

17 Citations (SciVal)
93 Downloads (Pure)


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
Issue number1
Publication statusPublished - 1 Mar 2018


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

ASJC Scopus subject areas

  • Statistics and Probability
  • General Mathematics
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Multiple drawing multi-colour urns by stochastic approximation'. Together they form a unique fingerprint.

Cite this