An algebraic approach to Pólya processes
Annales de l'I.H.P. Probabilités et statistiques, Tome 44 (2008) no. 2, pp. 293-323.

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).

DOI : 10.1214/07-AIHP130
Classification : 60F15, 60F17, 60F25, 60G05, 60G42, 60J05, 68W40
Mots-clés : Pólya processes, Pólya-Eggenberger urn processes, strong asymptotics, finite difference transition operator, vector-valued martingale methods 
@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},
     pages = {293--323},
     publisher = {Gauthier-Villars},
     volume = {44},
     number = {2},
     year = {2008},
     doi = {10.1214/07-AIHP130},
     mrnumber = {2446325},
     zbl = {1185.60029},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1214/07-AIHP130/}
}
TY  - JOUR
AU  - Pouyanne, Nicolas
TI  - An algebraic approach to Pólya processes
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2008
SP  - 293
EP  - 323
VL  - 44
IS  - 2
PB  - Gauthier-Villars
UR  - http://archive.numdam.org/articles/10.1214/07-AIHP130/
DO  - 10.1214/07-AIHP130
LA  - en
ID  - AIHPB_2008__44_2_293_0
ER  - 
%0 Journal Article
%A Pouyanne, Nicolas
%T An algebraic approach to Pólya processes
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2008
%P 293-323
%V 44
%N 2
%I Gauthier-Villars
%U http://archive.numdam.org/articles/10.1214/07-AIHP130/
%R 10.1214/07-AIHP130
%G en
%F 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) no. 2, pp. 293-323. doi : 10.1214/07-AIHP130. http://archive.numdam.org/articles/10.1214/07-AIHP130/

[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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

[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 | Zbl

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

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

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

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

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

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

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

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

[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 | Zbl

[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.

Cité par Sources :