Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-01-09T01:29:37.875Z Has data issue: false hasContentIssue false
  • English
  • Français

Multiple drawing multi-colour urns by stochastic approximation

Part of: Sequential methods Limit theorems

Published online by Cambridge University Press:  28 March 2018

Nabil Lasmar ,
Cécile Mailler  and
Olfa Selmi
Nabil Lasmar*
Affiliation:
Institut Préparatoire aux Études d'Ingénieur
Cécile Mailler*
Affiliation:
University of Bath
Olfa Selmi*
Affiliation:
Faculté des Sciences de Monastir
*
* Postal address: Département des Mathématiques, Institut Préparatoire aux Études d'Ingénieur, Monastir, Tunisia.
** Postal address: Department of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, UK. Email address: [email protected]
*** Postal address: Département des Mathématiques, Faculté des Sciences de Monastir, Monastir, Tunisia.
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Multiple drawing Pólya urnlimit theoremstochastic approximationreinforced processdiscrete-time martingale

MSC classification

Primary: 60F05: Central limit and other weak theorems
Secondary: 60F15: Strong theorems 62L20: Stochastic approximation
Type
Research Papers
Information
Journal of Applied Probability , Volume 55 , Issue 1 , March 2018 , pp. 254 - 281
Copyright
Copyright © Applied Probability Trust 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Aguech, R., Lassmar, N. and Selmi, O. (2014). A generalized urn model with multiple drawing and random addition. Preprint. Google Scholar
[2]Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Statist. 39, 1801–1817. CrossRefGoogle Scholar
[3]Bose, A., Dasgupta, A. and Maulik, K. (2009). Strong laws for balanced triangular urns. J. Appl. Prob. 46, 571–584. Google Scholar
[4]Chen, M.-R. and Kuba, M. (2013). On generalized Pólya urn models. J. Appl. Prob. 50, 1169–1186. CrossRefGoogle Scholar
[5]Chen, M.-R. and Wei, C.-Z. (2005). A new urn model. J. Appl. Prob. 42, 964–976. Google Scholar
[6]Duflo, M. (1997). Random Iterative Models. Springer, Berlin. Google Scholar
[7]Eggenberger, F. and Pólya, G. (1923). Über die statistik verketteter vorgänge. Z. Angew. Math. Mech. 3, 279–289. Google Scholar
[8]Flajolet, P., Dumas, P. and Puyhaubert, V. (2006). Some exactly solvable models of urn process theory. In Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 59–118. Google Scholar
[9]Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stoch. Process. Appl. 110, 177–245. Google Scholar
[10]Janson, S. (2006). Limit theorems for triangular urn schemes. Prob. Theory Relat. Fields 134, 417–452. Google Scholar
[11]Kuba, M. and Mahmoud, H. M. (2017). Two-color balanced affine urn models with multiple drawings. Adv. Appl. Math. 90, 1–26. CrossRefGoogle Scholar
[12]Kuba, M. and Sulzbach, H. (2017). On martingale tail sums in affine two-color urn models with multiple drawings. J. Appl. Prob. 54, 96–117. Google Scholar
[13]Kuba, M., Mahmoud, H. and Panholzer, A. (2013). Analysis of a generalized Friedman's urn with multiple drawings. Discrete Appl. Math. 161, 2968–2984. CrossRefGoogle Scholar
[14]Laruelle, S. and Pagès, G. (2013). Randomized urn models revisited using stochastic approximation. Ann. Appl. Prob. 23, 1409–1436. (Addendum and corrigendum: 27 (2017), 1296–1298.) CrossRefGoogle Scholar
[15]Laruelle, S. and Pagès, G. (2018). Randomized urn models revisited using stochastic approximation. Preprint. Available at https://arxiv.org/abs/1101.2786. Google Scholar
[16]Laslier, B. and Laslier, J.-F. (2017). Reinforcement learning from comparisons: three alternatives are enough, two are not. Ann. Appl. Prob. 27, 2907–2925. CrossRefGoogle Scholar
[17]Morcrette, B. (2012). Fully analyzing an algebraic Pólya urn model. In Latin 2012: Theoretical Informatics (Lecture Notes Comput. Sci. 7256), Springer, Heidelberg, pp. 568–581. Google Scholar
[18]Morcrette, B. and Mahmoud, H. M. (2012). Exactly solvable balanced tenable urns with random entries via the analytic methodology. In 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms, Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 219–232. Google Scholar
[19]Pemantle, R. (2007). A survey of random processes with reinforcement. Prob. Surveys 4, 1–79. Google Scholar
[20]Renlund, H. (2011). Limit theorems for stochastic approximation algorithms. Preprint. Available at https://arxiv.org/abs/1102.4741v1. Google Scholar
[21]Robbins, H. and Monro, S. (1951). A stochastic approximation method. Ann. Math. Statist. 22, 400–407. CrossRefGoogle Scholar
[22]Zhang, L.-X. (2016). Central limit theorems of a recursive stochastic algorithm with applications to adaptive designs. Ann. Appl. Prob. 26, 3630–3658. Google Scholar