zbMATH — the first resource for mathematics

An algebraic approach to Pólya processes. (English) Zbl 1185.60029
The paper deals with Pólya processes which are generalizations of Pólya-Eggenberger urn models with constant balance (i.e. for which the total number of added “balls” at any time is constant). The difference is that, instead counting a number of “balls”, positive real quantities corresponding to each “colour” are considered and entries of the replacement matrix \(R\) are not integers but reals. Then the process is normalized to have balance 1. A Pólya process is called small if 1 is a simple eigenvalue of the replacement matrix \(R\) and every other eigenvalue of \(R\) has real part not greater than \(1/2\). Otherwise, it is called large. The main results of the paper give an almost sure (and in \(L_p\), \(p\geq 1\)) asymptotic representation of a large Pólya process up to the order \(o(n^\sigma)\), where \(\sigma\) is the maximal real part of eigenvalues \(\lambda_2,\dots,\lambda_s\) of \(R\) except \(\lambda_1\) always being equal to 1. This asymptotic representation is described by finitely many random variables that appear as limits of martingales. The proofs of main results are based on estimates of moments of a Pólya process which have been obtained by an application of the spectral decomposition of a suitable finite difference transition operator on polynomial functions.

60F15 Strong limit theorems
60F17 Functional limit theorems; invariance principles
60F25 \(L^p\)-limit theorems
60G05 Foundations of stochastic processes
60G42 Martingales with discrete parameter
60J05 Discrete-time Markov processes on general state spaces
68W40 Analysis of algorithms
Full Text: DOI EuDML arXiv
[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. · Zbl 0185.46103 · doi:10.1214/aoms/1177698013
[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. · Zbl 0568.60010 · doi:10.1137/0606041
[3] P. Billingsley. Probability and Measure. Probability and Mathematical Statistics , 2nd edition. Wiley, New York, 1986. · Zbl 0649.60001
[4] B. Chauvin and N. Pouyanne. m -ary search trees when m \geq 27: a strong asymptotics for the space requirements. Random Structures Algorithms 24 (2004) 133-154. · Zbl 1037.60027 · doi:10.1002/rsa.10108
[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. · Zbl 0990.68052 · doi:10.1002/rsa.10005
[6] H.-H. Chern, M. Fuchs and H.-K. Hwang. Phase changes in random point quadtrees. ACM Trans. Algorithms 3 (2007) Art. 12. · Zbl 1321.68218 · doi:10.1145/1240233.1240235
[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 \geq 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. · Zbl 1073.60007 · doi:10.1214/009117905000000026
[10] B. Friedman. A simple urn model. Comm. Pure Appl. Math. 2 (1949) 59-70. · Zbl 0033.07101 · doi:10.1002/cpa.3160020103
[11] R. Gouet. Strong convergence of proportions in a multicolor Pòlya urn. J. Appl. Probab. 34 (1997) 426-435. · Zbl 0884.60028 · doi:10.2307/3215382
[12] R. L. Graham, D. E. Knuth and O. Patashnik. Concrete Mathematics , 2nd edition. Addison-Wesley, Reading, MA, 1995. · Zbl 0836.00001
[13] P. Hall and C. C. Heyde. Martingale Limit Theory and Its Applications . Academic Press, New York, 1980. · 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. · Zbl 1075.60109 · doi:10.1016/j.spa.2003.12.002
[15] S. Janson. Congruence properties of depths in some random trees. ALEA Lat. Am. J. Probab. Math. Stat. 1 (2006) 347-366. · Zbl 1104.60300
[16] S. Janson. Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 (2005) 417-452. · Zbl 1112.60012 · doi:10.1007/s00440-005-0442-7
[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
[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). · 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.