Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T12:52:40.718Z Has data issue: false hasContentIssue false
  • English
  • Français

Linear de-preferential urn models

Part of: Stochastic processes Limit theorems

Published online by Cambridge University Press:  29 November 2018

Antar Bandyopadhyay  and
Gursharn Kaur
Antar Bandyopadhyay*
Affiliation:
Indian Statistical Institute
Gursharn Kaur*
Affiliation:
Indian Statistical Institute
*
* Postal address: Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Delhi Centre, 7 SJS Sansanwal Marg, New Delhi 110016, India.
* Postal address: Theoretical Statistics and Mathematics Unit, Indian Statistical Institute, Delhi Centre, 7 SJS Sansanwal Marg, New Delhi 110016, India.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we consider a new type of urn scheme, where the selection probabilities are proportional to a weight function, which is linear but decreasing in the proportion of existing colours. We refer to it as the de-preferential urn scheme. We establish the almost-sure limit of the random configuration for any balanced replacement matrix R. In particular, we show that the limiting configuration is uniform on the set of colours if and only if R is a doubly stochastic matrix. We further establish the almost-sure limit of the vector of colour counts and prove central limit theorems for the random configuration as well as for the colour counts.

Keywords

Central limit theoremde-preferential urnstrong law of large numbersurn model

MSC classification

Primary: 60F05: Central limit and other weak theorems 60F15: Strong theorems
Secondary: 60G57: Random measures
Type
Original Article
Information
Advances in Applied Probability , Volume 50 , Issue 4 , December 2018 , pp. 1176 - 1192
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]Ahlberg, D.,Sidoravicius, V. and Tykesson, J. (2014).Bernoulli and self-destructive percolation on non-amenable graphs.Electron. Commun. Prob. 19, 6pp.Google Scholar
[2]Ahlberg, D.,Duminil-Copin, H.,Kozma, G. and Sidoravicius, V. (2015).Seven-dimensional forest fires.Ann. Inst. H. Poincaré Prob. Statist. 51,862–866.Google Scholar
[3]Albert, R. and Barabási, A.-L. (2002).Statistical mechanics of complex networks.Rev. Modern Phys. 74,47–97.Google Scholar
[4]Aldous, D. J. (2000).The percolation process on a tree where infinite clusters are frozen.Math. Proc. Camb. Phil. Soc. 128,465–477.Google Scholar
[5]Apostol, T. M. (1974).Mathematical Analysis,2nd edn.Addison-Wesley,Reading, MA.Google Scholar
[6]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.Google Scholar
[7]Bagchi, A. and Pal, A. K. (1985).Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures.SIAM J. Algebraic Discrete Methods 6,394–405.Google Scholar
[8]Bai, Z.-D. and Hu, F. (2005).Asymptotics in randomized URN models.Ann. Appl. Prob. 15,914–940.Google Scholar
[9]Bandyopadhyay, A. and Sen, S. (2017). De-preferential attachment random graphs. Preprint.Google Scholar
[10]Bandyopadhyay, A. (2006).A necessary and sufficient condition for the tail-triviality of a recursive tree process.Sankhyā 68,1–23.Google Scholar
[11]Bandyopadhyay, A. and Thacker, D. (2014).Rate of convergence and large deviation for the infinite color Pólya urn schemes.Statist. Prob. Lett. 92,232–240.Google Scholar
[12]Bandyopadhyay, A. and Thacker, D. (2016). A new approach to Pólya urn schemes and its infinite color generalization. Preprint. Available at https://arxiv.org/abs/1606.05317v1.Google Scholar
[13]Bandyopadhyay, A. and Thacker, D. (2017).Pólya urn schemes with infinitely many colors.Bernoulli 23,3243–3267.Google Scholar
[14]Barabási, A.-L. and Albert, R. (1999).Emergence of scaling in random networks.Science 286,509–512.Google Scholar
[15]Billingsley, P. (1995).Probability and Measure,3rd edn.John Wiley,New York.Google Scholar
[16]Bose, A.,Dasgupta, A. and Maulik, K. (2009).Multicolor urn models with reducible replacement matrices.Bernoulli 15,279–295.Google Scholar
[17]Bose, A.,Dasgupta, A. and Maulik, K. (2009).Strong laws for balanced triangular urns.J. Appl. Prob. 46,571–584.Google Scholar
[18]Bressaud, X. and Fournier, N. (2010).Asymptotics of one-dimensional forest fire processes.Ann. Prob. 38,1783–1816.Google Scholar
[19]Bressaud, X. and Fournier, N. (2014).A mean-field forest-fire model.ALEA 11,589–614.Google Scholar
[20]Chen, M.-R.,Hsiau, S.-R. and Yang, T.-H. (2014).A new two-urn model.J. Appl. Prob. 51,590–597.Google Scholar
[21]Collevecchio, A.,Cotar, C. and LiCalzi, M. (2013).On a preferential attachment and generalized Pólya's urn model.Ann. Appl. Prob. 23,1219–1253.Google Scholar
[22]Cotar, C. and Limic, V. (2009).Attraction time for strongly reinforced walks.Ann. Appl. Prob. 19,1972–2007.Google Scholar
[23]Crane, E.,Freeman, N. and Tóth, B. (2015).Cluster growth in the dynamical Erdős-Rényi process with forest fires.Electron. J. Prob. 20, 33pp.Google Scholar
[24]Crane, E. et al. (2011).The simple harmonic urn.Ann. Prob. 39,2119–2177.Google Scholar
[25]Dasgupta, A. and Maulik, K. (2011).Strong laws for urn models with balanced replacement matrices.Electron. J. Prob. 16,1723–1749.Google Scholar
[26]Davis, B. (1990).Reinforced random walk.Prob. Theory Relat. Fields 84,203–229.Google Scholar
[27]Dürre, M. (2006).Existence of multi-dimensional infinite volume self-organized critical forest-fire models.Electron. J. Prob. 11,513–539.Google Scholar
[28]Dürre, M. (2006).Uniqueness of multi-dimensional infinite volume self-organized critical forest-fire models.Electron. Commun. Prob. 11,304–315.Google Scholar
[29]Ehrenfest, P. and Ehrenfest, T. (1990).The Conceptual Foundations of the Statistical Approach in Mechanics.Dover Publications,New York.Google Scholar
[30]Flajolet, P.,Dumas, P. and Puyhaubert, V. (2006).Some exactly solvable models of urn process theory. In 4th Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (Discrete Math. Theoret. Comput. Sci. Proc. AG),Assoc. Discrete Math. Theoret. Comput. Sci.,Nancy, pp. 59–118.Google Scholar
[31]Freedman, D. A. (1965).Bernard Friedman's urn.Ann. Math. Statist. 36,956–970.Google Scholar
[32]Friedman, B. (1949).A simple urn model.Commun. Pure Appl. Math. 2,59–70.Google Scholar
[33]Gouet, R. (1997).Strong convergence of proportions in a multicolor Pólya urn.J. Appl. Prob. 34,426–435.Google Scholar
[34]Hall, P. and Heyde, C. C. (1980).Martingale Limit Theory and Its Application.Academic Press,New York.Google Scholar
[35]Janson, S. (2004).Functional limit theorems for multitype branching processes and generalized Pólya urns.Stoch. Process. Appl. 110,177–245.Google Scholar
[36]Janson, S. (2006).Limit theorems for triangular urn schemes.Prob. Theory Relat. Fields 134,417–452.Google Scholar
[37]Kingman, J. F. C. (1999).Martingales in the OK Corral.Bull. London Math. Soc. 31,601–606.Google Scholar
[38]Kingman, J. F. C. and Volkov, S. E. (2003).Solution to the OK Corral model via decoupling of Friedman's urn.J. Theoret. Prob. 16,267–276.Google Scholar
[39]Laruelle, S. and Pagüs, G. (2013).Randomized urn models revisited using stochastic approximation.Ann. Appl. Prob. 23,1409–1436.Google Scholar
[40]Launay, M. and Limic, V. (2012). Generalized interacting urn models. Preprint. Available at https://arxiv.org/abs/1207.5635v1.Google Scholar
[41]Limic, V. (2003).Attracting edge property for a class of reinforced random walks.Ann. Prob. 31,1615–1654.Google Scholar
[42]Limic, V. and Tarrüs, P. (2007).Attracting edge and strongly edge reinforced walks.Ann. Prob. 35,1783–1806.Google Scholar
[43]Luczak, M. J. and McDiarmid, C. (2005).On the power of two choices: balls and bins in continuous time.Ann. Appl. Prob. 15,1733–1764.Google Scholar
[44]Luczak, M. J. and McDiarmid, C. (2006).On the maximum queue length in the supermarket model.Ann. Prob. 34,493–527.Google Scholar
[45]Mahmoud, H. M. (2009).Pólya Urn Models.CRC Press,Boca Raton, FL.Google Scholar
[46]Pemantle, R. (1990).A time-dependent version of Pólya's urn.J. Theoret. Prob. 3,627–637.Google Scholar
[47]Pemantle, R. (2007).A survey of random processes with reinforcement.Prob. Surveys 4,1–79.Google Scholar
[48]Pólya, G. (1930).Sur quelques points de la théorie des probabilités.Ann. Inst. H. Poincaré Prob. Statist. 1,117–161 (in French).Google Scholar
[49]Ráth, B. and Tóth, B. (2009).Erdős-Rényi random graphs + forest fires = self-organized criticality.Electron. J. Prob. 14,1290–1327.Google Scholar
[50]Sevim, V. and Rikvold, P. A. (2006).Effects of preference for attachment to low-degree nodes on the degree distributions of a growing directed network and a simple food-web model.Phys. Rev. E 73, 056115.Google Scholar
[51]Sevim, V. and Rikvold, P. A. (2008).Network growth with preferential attachment for high indegree and low outdegree.Physica A 387,2631–2636.Google Scholar
[52]Van den Berg, J. and Brouwer, R. (2004).Self-destructive percolation.Random Structures Algorithms 24,480–501.Google Scholar
[53]Van den Berg, J. and Brouwer, R. (2006).Self-organized forest-fires near the critical time.Commun. Math. Phys. 267,265–277.Google Scholar
[54]Van den Berg, J. and de Lima, B. N. B. (2009).Linear lower bounds for δc(p) for a class of 2D self-destructive percolation models.Random Structures Algorithms 34,520–526.Google Scholar
[55]Van den Berg, J. and Járai, A. A. (2005).On the asymptotic density in a one-dimensional self-organized critical forest-fire model.Commun. Math. Phys. 253,633–644.Google Scholar
[56]Van den Berg, J. and Nolin, P. (2017).Two-dimensional volume-frozen percolation: exceptional scales.Ann. Appl. Prob. 27,91–108.Google Scholar
[57]Van den Berg, J.,Brouwer, R. and Vágvölgyi, B. (2008).Box-crossings and continuity results for self-destructive percolation in the plane. In In and Out of Equilibrium. 2 (Progress Prob. 60),Birkhäuser,Basel, pp. 117–135.Google Scholar
[58]Van den Berg, J.,de Lima, B. N. B. and Nolin, P. (2012).A percolation process on the square lattice where large finite clusters are frozen.Random Structures Algorithms 40,220–226.Google Scholar
[59]Van den Berg, J.,Kiss, D. and Nolin, P. (2012).A percolation process on the binary tree where large finite clusters are frozen.Electron. Commun. Prob. 17, 11pp.Google Scholar
[60]Williams, D. and McIlroy, P. (1998).The OK Corral and the power of the law (a curious Poisson-kernel formula for a parabolic equation).Bull. London Math. Soc. 30,166–170.Google Scholar