An algebraic approach to Pólya processes
Pouyanne, Nicolas
Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008), p. 293-323 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Les processus de Pólya sont une généralisation naturelle des modèles d'urnes de Pólya-Eggenberger. Cet article présente une nouvelle approche de leur comportement asymptotique via les moments, basée sur la décomposition spectrale d'un opérateur aux différences finies sur des espaces de polynômes. En particulier, elle fournit de nouveaux résultats sur les grands processus (un processus de Pólya est dit petit lorsque 1 est valeur propre simple de sa matrice de remplacement et lorsque toutes les autres valeurs propres ont une partie réelle ≤1/2 ; sinon, on dit qu’il est grand).

Pólya processes are natural generalizations of Pólya-Eggenberger urn models. This article presents a new approach of their asymptotic behaviour via moments, based on the spectral decomposition of a suitable finite difference transition operator on polynomial functions. Especially, it provides new results for large processes (a Pólya process is called small when 1 is a simple eigenvalue of its replacement matrix and when any other eigenvalue has a real part ≤1/2; otherwise, it is called large).

Publié le : 2008-01-01
DOI : https://doi.org/10.1214/07-AIHP130
Classification:  60F15,  60F17,  60F25,  60G05,  60G42,  60J05,  68W40 
@article{AIHPB_2008__44_2_293_0,
     author = {Pouyanne, Nicolas},
     title = {An algebraic approach to P\'olya processes},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {44},
     year = {2008},
     pages = {293-323},
     doi = {10.1214/07-AIHP130},
     mrnumber = {2446325},
     zbl = {1185.60029},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_2008__44_2_293_0}
}

Pouyanne, Nicolas. An algebraic approach to Pólya processes. Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008) pp. 293-323. doi : 10.1214/07-AIHP130. http://gdmltest.u-ga.fr/item/AIHPB_2008__44_2_293_0/

[1] K. B. Athreya and S. Karlin. Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Statist. 39 (1968) 1801-1817. | MR 232455 | Zbl 0185.46103

[2] A. Bagchi and A. K. Pal. Asymptotic normality in the generalized Pólya-Eggenberger urn model, with an application to computer data structures. SIAM J. Algebraic Discrete Methods 6 (1985) 394-405. | MR 791169 | Zbl 0568.60010

[3] P. Billingsley. Probability and Measure. Probability and Mathematical Statistics, 2nd edition. Wiley, New York, 1986. | MR 830424 | Zbl 0649.60001

[4] B. Chauvin and N. Pouyanne. m-ary search trees when m≥27: a strong asymptotics for the space requirements. Random Structures Algorithms 24 (2004) 133-154. | MR 2035872 | Zbl 1037.60027

[5] H.-H. Chern and H.-K. Hwang. Phase changes in random m-ary search trees and generalized quicksort. Random Structures Algorithms 19 (2001) 316-358. | MR 1871558 | Zbl 0990.68052

[6] H.-H. Chern, M. Fuchs and H.-K. Hwang. Phase changes in random point quadtrees. ACM Trans. Algorithms 3 (2007) Art. 12. | MR 2335295

[7] F. Eggenberger and G. Pólya. Ueber die Statistik verketter Vorgänge. Z. Angew. Math. Mech. 1 (1923) 279-289. | JFM 49.0382.01

[8] J. A. Fill and N. Kapur. The space requirements of m-ary search trees: distributional asymptotics for m≥27. Submitted. Available at http://arxiv.org/abs/math/0405144v1.

[9] P. Flajolet, J. Gabarró and H. Pekari. Analytic urns. Ann. Probab. 33 (2005) 1200-1233. | MR 2135318 | Zbl 1073.60007

[10] B. Friedman. A simple urn model. Comm. Pure Appl. Math. 2 (1949) 59-70. | MR 30144 | Zbl 0033.07101

[11] R. Gouet. Strong convergence of proportions in a multicolor Pòlya urn. J. Appl. Probab. 34 (1997) 426-435. | MR 1447347 | Zbl 0884.60028

[12] R. L. Graham, D. E. Knuth and O. Patashnik. Concrete Mathematics, 2nd edition. Addison-Wesley, Reading, MA, 1995. | MR 1397498 | Zbl 0668.00003

[13] P. Hall and C. C. Heyde. Martingale Limit Theory and Its Applications. Academic Press, New York, 1980. | MR 624435 | Zbl 0462.60045

[14] S. Janson. Functional limit theorem for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 (2004) 177-245. | MR 2040966 | Zbl 1075.60109

[15] S. Janson. Congruence properties of depths in some random trees. ALEA Lat. Am. J. Probab. Math. Stat. 1 (2006) 347-366. | MR 2249661 | Zbl 1104.60300

[16] S. Janson. Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 (2005) 417-452. | MR 2226887 | Zbl 1112.60012

[17] G. Pólya. Sur quelques points de la théorie des probabilités. Ann. Inst. H. Poincaré 1 (1930) 117-161. | JFM 57.0610.02 | Numdam | MR 1507985

[18] N. Pouyanne. Classification of large Pólya-Eggenberger urns with regard to their asymptotics. In: Internat. Conf. on Analysis of Algorithms. Discrete Math. Theor. Comput. Sci. Proc., AD. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 275-285 (electronic). | MR 2193125 | Zbl 1096.60007

[19] V. Puyhaubert. Modèles d'urnes et phénomènes de seuils en combinatoire analytique. Thèse de l'Ecole Polytechnique. Available at http://www.imprimerie.polytechnique.fr/Theses/Files/Puyhaubert.pdf, 2005.