Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-23T22:46:46.418Z Has data issue: false hasContentIssue false
  • English
  • Français

Central limit theorems for a hypergeometric randomly reinforced urn

Part of: Stochastic processes Probability theory on algebraic and topological structures Limit theorems

Published online by Cambridge University Press:  24 October 2016

Irene Crimaldi
Irene Crimaldi*
Affiliation:
IMT School for Advanced Studies Lucca
*
* Postal address: IMT School for Advanced Studies Lucca, Piazza San Ponziano 6, 55100 Lucca, Italy. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a variant of the randomly reinforced urn where more balls can be simultaneously drawn out and balls of different colors can be simultaneously added. More precisely, at each time-step, the conditional distribution of the number of extracted balls of a certain color, given the past, is assumed to be hypergeometric. We prove some central limit theorems in the sense of stable convergence and of almost sure conditional convergence, which are stronger than convergence in distribution. The proven results provide asymptotic confidence intervals for the limit proportion, whose distribution is generally unknown. Moreover, we also consider the case of more urns subjected to some random common factors.

Keywords

Central limit theoremPòlya urnpreferential attachmentrandom process with reinforcementrandomly reinforced urnstable convergence

MSC classification

Primary: 60F05: Central limit and other weak theorems
Secondary: 60G57: Random measures 60B10: Convergence of probability measures 60G42: Martingales with discrete parameter
Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 3 , September 2016 , pp. 899 - 913
Copyright
Copyright © Applied Probability Trust 2016 

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] Aldous, D. J. and Eagleson, G. K. (1978).On mixing and stability of limit theorems.Ann. Prob. 6,325–331.Google Scholar
[2] Aletti, G.,May, C. and Secchi, P. (2009).A central limit theorem, and related results, for a two-color randomly reinforced urn.Adv. Appl. Prob. 41,829–844.Google Scholar
[3] Aoudia, D. A. and Perron, E. (2012).A new randomized Pólya urn model.Appl. Math. 3,2118–2122.Google Scholar
[4] Arthur, W. B. (1989 ).Competing technologies, increasing returns, and lock-in by historical events.Econom. J. 99,!116–131.Google Scholar
[5] Bai, Z.-D. and Hu, F. (2005).Asymptotics in randomized URN models.Ann. Appl. Prob. 15,914–940.Google Scholar
[6] Bai, Z. D.,Hu, F. and Rosenberger, W. F. (2002).Asymptotic properties of adaptive designs for clinical trials with delayed response.Ann. Statist. 30,122–139.Google Scholar
[7] Banerjee, A.,Burlina, P. and Alajaji, F. (1999).Image segmentation and labeling using the Pólya urn model.IEEE Trans. Image Process. 8,1243–1253.CrossRefGoogle ScholarPubMed
[8] Bassetti, F.,Crimaldi, I. and Leisen, F. (2010).Conditionally identically distributed species sampling sequences.Adv. Appl. Prob. 42,433–459.Google Scholar
[9] Beggs, A. W. (2005).On the convergence of reinforcement learning.J. Econom. Theory 122,1–36.Google Scholar
[10] Berti, P.,Pratelli, L. and Rigo, P. (2004).Limit theorems for a class of identically distributed random variables.Ann. Prob. 32,2029–2052.Google Scholar
[11] Berti, P.,crimaldi, I.,Pratelli, L. and Rigo, P. (2009).Rate of convergence of predictive distributions for dependent data.Bernoulli 15,1351–1367.CrossRefGoogle Scholar
[12] Berti, P.,crimaldi, I.,Pratelli, L. and Rigo, P. (2010).Central limit theorems for multicolor urns with dominated colors.Stoch. Process. Appl. 120,1473–1491.Google Scholar
[13] Berti, P.,crimaldi, I.,Pratelli, L. and Rigo, P. (2011).A central limit theorem and its applications to multicolor randomly reinforced urns.J. Appl. Prob. 48,527–546.Google Scholar
[14] Berti, P.,crimaldi, I.,Pratelli, L. and Rigo, P. (2015).Central limit theorems for an Indian buffet model with random weights.Ann. Appl. Prob. 25,523–547.Google Scholar
[15] Blackwell, D. and Dubins, L. (1962).Merging of opinions with increasing information.Ann. Math. Statist. 33,882–886.Google Scholar
[16] Boldi, P.,Crimaldi, I. and Monti, C. (2016).A network model characterized by a latent attribute structure with competition.Inf. Sci. 354,236–256.Google Scholar
[17] Bose, A.,Dasgupta, A. and Maulik, K. (2009).Multicolor urn models with reducible replacement matrices.Bernoulli 15,279–295.Google Scholar
[18] Caldarelli, G.,Chessa, A.,Crimaldi, I. and Pammolli, F. (2013).Weighted networks as randomly reinforced urn processes.Phys. Rev. E 87,020106(R).CrossRefGoogle ScholarPubMed
[19] Chauvin, B.,Pouyanne, N. and Sahnoun, R. (2011).Limit distributions for large Pólya urns.Ann. Appl. Prob. 21,1–32.Google Scholar
[20] Chen, M.-R. and Kuba, M. (2013).On generalized Pólya urn models.J. Appl. Prob. 50,1169–1186.CrossRefGoogle Scholar
[21] Chen, M.-R. and Wei, C.-Z. (2005).A new urn model.J. Appl. Prob. 42,964–976.CrossRefGoogle Scholar
[22] Collevecchio, A.,Cotar, C. and LiCalzi, M. (2013).On a preferential attachment and generalized Póolya's urn model.Ann. Appl. Prob. 23,1219–1253.Google Scholar
[23] Crimaldi, I. (2009).An almost sure conditional convergence result and an application to a generalized Pólya urn.Internat. Math. Forum 4,1139–1156.Google Scholar
[24] Crimaldi, I. and Leisen, F. (2008).Asymptotic results for a generalized Pólya urn with ‘multi-updating’ and applications to clinical trials.Commun. Statist. Theory Meth. 37,2777–2794.Google Scholar
[25] Crimaldi, I.,Letta, G. and Pratelli, L. (2007).A strong form of stable convergence.Séminaire de Probabilités XL, (Lecture Notes Math. 1899}), Springer,Berlin, pp.203–225.CrossRefGoogle Scholar
[26] Crimaldi, I. et al. (2016).Modeling networks with a growing feature-structure. Submitted.Google Scholar
[27] Dasgupta, A. and Maulik, K. (2011).Strong laws for urn models with balanced replacement matrices.Electron. J. Prob. 16,1723–1749.CrossRefGoogle Scholar
[28] Durham, S. D.,Flournoy, N. and Li, W. (1998).A sequential design for maximizing the probability of a favourable response..Canad. J. Statist. 26,479–495.CrossRefGoogle Scholar
[29] Eggenberger, F. and Pólya, G. (1923).Über die statistik verketteter vorgänge.Z. Angew. Math. Mech. 3,279–289.Google Scholar
[30] Erev, I. and Roth, A. E. (1998).Predicting how people play games: reinforcement learning in experimental games with unique, mixed strategy equilibria.Amer. Econom. Rev. 88,848–881.Google Scholar
[31] Feigin, P. D. (1985).Stable convergence of semimartingales.Stoch. Process. Appl. 19,125–134.Google Scholar
[32] Hall, P. and Heyde, C. C. (1980).Martingale Limit Theory and Its Application ,Academic Press ,New York.Google Scholar
[33] Hopkins, E. and Posch, M. (2005).Attainability of boundary points under reinforcement learning.Games Econom. Behav. 53,110–125.CrossRefGoogle Scholar
[34] Hu, F. and Rosenberger, W. F. (2006).The Theory of Response-Adaptive Randomization in Clinical Trials.John Wiley,Hoboken, NJ.Google Scholar
[35] Jacod, J. and Mémin, J. (1981).Sur un type de convergence intermédiaire entre la convergence en loi et la convergence en probabilité. InSéminaire de Probabilités XV (Lecture Notes Math. 850).Springer,Berlin, pp.529–546.Google Scholar
[36] Janson, S. (2006).Limit theorems for triangular urn schemes.Prob. Theory Relat. Fields 134,417–452.Google Scholar
[37] Laruelle, S. and Pagès, G. (2013).Randomized urn models revisited using stochastic approximation.Ann. Appl. Prob. 23,1409–1436.Google Scholar
[38] Mahmoud, H. M. (2009).Pólya Urn Models.CRC,Boca Raton, FL.Google Scholar
[39] Martin, C. F. and Ho, Y. C. (2002).Value of information in the Pólya urn process.Inf. Sci. 147,65–90.CrossRefGoogle Scholar
[40] May, C. and Flournoy, N. (2009).Asymptotics in response-adaptive designs generated by a two-color, randomly reinforced urn.Ann. Statist. 37,1058–1078.Google Scholar
[41] Muliere, P.,Paganoni, A. M. and Secchi, P. (2006).A randomly reinforced urn.J. Statist. Planning Inf. 136,1853–1874.Google Scholar
[42] Peccati, G. and Taqqu, M. S. (2008).Stable convergence of multiple Wiener–Itô integrals.J. Theoret. Prob. 21,527–570.Google Scholar
[43] Pemantle, R. (2007).A survey of random processes with reinforcement.Prob. Surveys 4,1–79.CrossRefGoogle Scholar
[44] Pólya, G. (1930).Sur quelques points de la théorie des probabilités.Ann. Inst. H. Poincaré 1,117–161.Google Scholar
[45] Rényi, A. (1963).On stable sequences of events.Sankhyā A 25,293–302.Google Scholar
[46] Skyrms, B. and Pemantle, R. (2000). A dynamic model of social network formation.Proc. Nat. Acad. Sci. USA 97,9340–9346.Google Scholar
[47] Xeu, J. (2006).A Pólya urn model of conformity.Working Paper 0614. Faculty of Economics, University of Cambridge.Google Scholar
[48] Zhang, L.-X. (2014).A Gaussian process approximation for two-color randomly reinforced urns.Electron. J. Prob. 19,86.Google Scholar
[49] Zhang, L.-X.,Hu, F. and Cheung, S. H. (2006).Asymptotic theorems of sequential estimation-adjusted urn models.Ann. Appl. Prob. 16,340–369.Google Scholar
[50] Zhang, L.-X.,Hu, F.,Cheung, S. H.and Chan, W. S. (2014).Asymptotic properties of multicolor randomly reinforced Pólya urns.Adv. Appl. Prob. 46,585–602.Google Scholar