Multiple drawing multi-colour urns by stochastic approximation

Nabil Lasmar, Cecile Mailler, Olfa Selmi

Research output: Contribution to journalArticle

4 Citations (Scopus)
45 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

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

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

  • Cite this