Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T11:42:33.394Z Has data issue: false hasContentIssue false
  • English
  • Français

Strong Convergence for URN Models with Reducible Replacement Policy

Part of:Limit theorems

Published online by Cambridge University Press:  14 July 2016

R. Abraham,
J. S. Dhersin and
B. Ycart
R. Abraham*
Affiliation:
Université d'Orléans
J. S. Dhersin*
Affiliation:
Université René Descartes
B. Ycart*
Affiliation:
Université Joseph Fourier
*
∗ Postal address: MAPMO, CNRS UMR 6628, Université d'Orléans, France. Email address: romain.abraham@univ-orleans.fr
∗∗ Postal address: MAP5, CNRS UMR 8145, Université René Descartes, Paris, France. Email address: jean-stephane.dhersin@univ-paris5.fr
∗∗∗ Postal address: LJK, CNRS UMR 5224, Université Joseph Fourier, Grenoble, France. Email address: bernard.ycart@ujf-grenoble.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A multitype urn scheme with random replacements is considered. Each time a ball is picked, another ball is added, and its type is chosen according to the transition probabilities of a reducible Markov chain. The vector of frequencies is shown to converge almost surely to a random element of the set of stationary measures of the Markov chain. Its probability distribution is characterized as the solution to a fixed point problem. It is proved to be Dirichlet in the particular case of a single transient state to which no return is possible. This is no longer the case, however, as soon as returns to transient states are allowed.

Keywords

Urn modelMarkov chainstrong convergence

MSC classification

Secondary:60F15: Strong theorems

Information

Type
Research Article
Information
Journal of Applied Probability , Volume 44 , Issue 3 , September 2007, pp. 652 - 660
Copyright
Copyright © Applied Probability Trust 2007 

References

[1] Bai, Z. D. and Hu, F. (2005). Asymptotics in randomized urn models. Ann. Appl. Prob. 15, 914–940.Google Scholar
[2] Bai, Z. D., Hu, F. and Zhang, L. X. (2002). Gaussian approximation theorems for urn models and their applications. Ann. Appl. Prob. 12, 1149–1173.Google Scholar
[3] Benaïm, M., Schreiber, S. and Tarrès, P. (2004). Generalized urn models of evolutionary processes. Ann. Appl. Prob. 14, 1455–1478.Google Scholar
[4] Chamayou, J.-F. and Letac, G. (1991). Explicit stationary distributions for compositions of random functions and product of random matrices. J. Theoret. Prob. 4, 3–36.Google Scholar
[5] Delyon, B. (1996). General results on the convergence of stochastic algorithms. IEEE Trans. Automatic Control 41, 1245–1255.CrossRefGoogle Scholar
[6] Duflo, M. (1997). Random Iterative Models. Springer, New York.Google Scholar
[7] Eggenberger, F. and Pólya, G. (1928). Sur l'interprétation de certaines courbes de fréquence. C. R. Acad. Sci. Paris 187, 870–872.Google Scholar
[8] Gouet, R. (1993). Martingale functional central limit theorems for a generalized {Pólya} urn. Ann. Prob. 21, 1624–1639.CrossRefGoogle Scholar
[9] Gouet, R. (1997). Strong convergence of proportions in a multicolor {Pólya} urn. J. Appl. Prob. 34, 426–435.Google Scholar
[10] Higueras, I., Moler, J., Plo, F. and {San, Miguel, M.} (2003). Urn models and differential algebraic equations. J. Appl. Prob. 40, 401–412.Google Scholar
[11] Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized {Pólya} urns. Stoch. Process. Appl. 110, 177–245.Google Scholar
[12] Johnson, N. L. and Kotz, S. (1977). Urn Models and Their Application. John Wiley, New York.Google Scholar
[13] Kushner, H. J. and Yin, G. G. (1997). Stochastic Approximation Algorithms and Applications. Springer, New York.Google Scholar
[14] Letac, G. (1986). A contraction principle for certain Markov chains and its applications. Contemp. Math. 50, 263–273.Google Scholar
[15] Pitman, J. (1996). Some developments of the {Blackwell–MacQueen} urn scheme. In Statistics, Probability and Game Theory (IMS Lecture Notes Monogr. Ser. 30), Institute of Mathematical Statistics, Hayward, CA, pp. 245–267.Google Scholar
[16] Schreiber, S. (2001). Urn models, replicator processes and random genetic drift. SIAM J. Appl. Math. 61, 2148–2167.Google Scholar