An algebraic approach to Pólya processes

Nicolas Pouyanne

Annales de l'I.H.P. Probabilités et statistiques (2008)

  • Volume: 44, Issue: 2, page 293-323
  • ISSN: 0246-0203

Abstract

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

How to cite

top

Pouyanne, Nicolas. "An algebraic approach to Pólya processes." Annales de l'I.H.P. Probabilités et statistiques 44.2 (2008): 293-323. <http://eudml.org/doc/77971>.

@article{Pouyanne2008,
abstract = {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).},
author = {Pouyanne, Nicolas},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {Pólya processes; Pólya–Eggenberger urn processes; strong asymptotics; finite difference transition operator; vector-valued martingale methods; Pólya-Eggenberger urn model; Pólya process; vector-valued martingale; transition operator; spectral decomposition},
language = {eng},
number = {2},
pages = {293-323},
publisher = {Gauthier-Villars},
title = {An algebraic approach to Pólya processes},
url = {http://eudml.org/doc/77971},
volume = {44},
year = {2008},
}

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
PB - Gauthier-Villars
VL - 44
IS - 2
SP - 293
EP - 323
AB - 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).
LA - eng
KW - Pólya processes; Pólya–Eggenberger urn processes; strong asymptotics; finite difference transition operator; vector-valued martingale methods; Pólya-Eggenberger urn model; Pólya process; vector-valued martingale; transition operator; spectral decomposition
UR - http://eudml.org/doc/77971
ER -

References

top
  1. [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. Zbl0185.46103MR232455
  2. [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. Zbl0568.60010MR791169
  3. [3] P. Billingsley. Probability and Measure. Probability and Mathematical Statistics, 2nd edition. Wiley, New York, 1986. Zbl0649.60001MR830424
  4. [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. Zbl1037.60027MR2035872
  5. [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. Zbl0990.68052MR1871558
  6. [6] H.-H. Chern, M. Fuchs and H.-K. Hwang. Phase changes in random point quadtrees. ACM Trans. Algorithms 3 (2007) Art. 12. Zbl1321.68218MR2335295
  7. [7] F. Eggenberger and G. Pólya. Ueber die Statistik verketter Vorgänge. Z. Angew. Math. Mech. 1 (1923) 279–289. Zbl49.0382.01JFM49.0382.01
  8. [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. Zbl1101.68018
  9. [9] P. Flajolet, J. Gabarró and H. Pekari. Analytic urns. Ann. Probab. 33 (2005) 1200–1233. Zbl1073.60007MR2135318
  10. [10] B. Friedman. A simple urn model. Comm. Pure Appl. Math. 2 (1949) 59–70. Zbl0033.07101MR30144
  11. [11] R. Gouet. Strong convergence of proportions in a multicolor Pòlya urn. J. Appl. Probab. 34 (1997) 426–435. Zbl0884.60028MR1447347
  12. [12] R. L. Graham, D. E. Knuth and O. Patashnik. Concrete Mathematics, 2nd edition. Addison-Wesley, Reading, MA, 1995. Zbl0668.00003MR1397498
  13. [13] P. Hall and C. C. Heyde. Martingale Limit Theory and Its Applications. Academic Press, New York, 1980. Zbl0462.60045MR624435
  14. [14] S. Janson. Functional limit theorem for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl. 110 (2004) 177–245. Zbl1075.60109MR2040966
  15. [15] S. Janson. Congruence properties of depths in some random trees. ALEA Lat. Am. J. Probab. Math. Stat. 1 (2006) 347–366. Zbl1104.60300MR2249661
  16. [16] S. Janson. Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 (2005) 417–452. Zbl1112.60012MR2226887
  17. [17] G. Pólya. Sur quelques points de la théorie des probabilités. Ann. Inst. H. Poincaré 1 (1930) 117–161. MR1507985JFM57.0610.02
  18. [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). Zbl1096.60007MR2193125
  19. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.