Geodesic
On the asymptotics of moments of linear random recurrences
Teoriâ slučajnyh processov, Tome 16 (2010) no. 2, pp. 106-119.

Voir la notice de l'article provenant de la source Math-Net.Ru

We propose a new method of analyzing the asymptotics of moments of certain linear random recurrences which is based on the technique of iterative functions. By using the method, we show that the moments of the number of collisions and the absorption time in the Poisson–Dirichlet coalescent behave like the powers of the "log star" function which grows slower than any iteration of the logarithm, and thereby we prove a weak law of large numbers. Finally, we discuss merits and limitations of the method and give several examples related to beta coalescents, recursive algorithms, and random trees.
Keywords: linear recurrence.
Mots-clés : Moments, Poisson–Dirichlet coalescent 
@article{THSP_2010_16_2_a10,
     author = {Alexander Marynych},
     title = {On the asymptotics of moments of linear random recurrences},
     journal = {Teori\^a slu\v{c}ajnyh processov},
     pages = {106--119},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/THSP_2010_16_2_a10/}
}
TY  - JOUR
AU  - Alexander Marynych
TI  - On the asymptotics of moments of linear random recurrences
JO  - Teoriâ slučajnyh processov
PY  - 2010
SP  - 106
EP  - 119
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/THSP_2010_16_2_a10/
LA  - en
ID  - THSP_2010_16_2_a10
ER  - 
%0 Journal Article
%A Alexander Marynych
%T On the asymptotics of moments of linear random recurrences
%J Teoriâ slučajnyh processov
%D 2010
%P 106-119
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/THSP_2010_16_2_a10/
%G en
%F THSP_2010_16_2_a10
Alexander Marynych. On the asymptotics of moments of linear random recurrences. Teoriâ slučajnyh processov, Tome 16 (2010) no. 2, pp. 106-119. http://geodesic.mathdoc.fr/item/THSP_2010_16_2_a10/

[1] V. Bruhn, Eine Methode zur asymptotischen Behandlungeiner Klasse von Rekursionsgleichungen mit einer Anwendung in der stochastischen Analyse des Quicksort-Algorithmus, Dissertation, Christian-Albrechts-UniversitP̈{a}t zu Kiel, 1996

[2] B. van Cutsem, B. Ycart, “Renewal-type behaviour of absorption times in Markov chains”, Adv. Appl. Prob., 26 (1994), 988–1005

[3] J.-F. Delmas, J.-S. Dhersin, A. Siri-Jegousse, “Asymptotic results on the length of coalescent trees”, Ann. Appl. Probab., 18 (2008), 997–-1025

[4] O. Devillers, “Randomization yields simple $O(n{\log}^* n)$ algorithms for difficult $\Omega(n)$ problems”, Internat. J. Comput. Geom. Appl., 2 (1992), 621–635

[5] M. Drmota, Random Trees: An Interplay between Combinatorics and Probability, Springer, Berlin, 2009

[6] M. Drmota, A. Iksanov,M. Moehle, U. Roesler, “Asymptotic results concerning the total branch length of the Bolthausen–Sznitman coalescent”, Stoch. Process. Appl., 117 (2007), 1404–1421

[7] M. Drmota, A. Iksanov, M. Moehle, U. Roesler, “A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree”, Random Struct. Algorithms, 34 (2009), 319–336

[8] P. Flajolet, R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2008

[9] A. V. Gnedin, “The Bernoulli sieve”, Bernoulli, 10 (2004), 79–96

[10] A. Gnedin, A. Iksanov, M. Möhle, “On asymptotics of exchangeable coalescents with multiple collisions”, J. Appl. Probab., 45 (2008), 1186–1195

[11] A. Gnedin, A. Iksanov, P. Negadajlov, U. Roesler, “The Bernoulli sieve revisited”, Ann. Appl. Prob., 19 (2009), 1634–1655

[12] A. Gnedin, Y. Yakubovich, “On the number of collisions in $\Lambda$-coalescents”, Electron. J. Probab., 12 (2007), 1547–1567

[13] B. Haas, G. Miermont, “Self-similar scaling limits of non-increasing Markov chains”, Bernoulli, 2010 (to appear)

[14] C. R. Hoar, “Quicksort”, The Computer Journal, 5:1 (1962), 10–16

[15] D. H. Greene, D. E. Knuth, Mathematics for the analysis of algorithms, Burkhäuser, Basel, 1990

[16] A. Iksanov, A. Marynych, M. Möhle, “On the number of collisions in beta(2,b)-coalescents”, Bernoulli, 15 (2009), 829–845

[17] A. Iksanov, M. Möhle, “On the number of jumps of random walks with a barrier”, Adv. Appl. Probab., 40 (2008), 206–228

[18] A. Iksanov, P. Negadajlov, “On the number of zero increments of a random walk with a barrier”, Discrete Math. Theor. Comput. Sci. Proceedings Series, AI, 2008, 247–254

[19] R. M. Karp, “Probabilistic recurrence relations”, Journal of the Association for Computer Machinery, 41 (1994), 1136–1150

[20] H. Kesten, “The number of distinguishable alleles according to the Ohta–Kimura model of neutral mutation”, J. Math. Biol., 10 (1980), 167–187

[21] H. Mahmoud, Evolution of random search trees, Wiley, New York, 1992

[22] A. Meir, J. W. Moon, “Cutting down recursive trees”, Math. Biosci., 21 (1974), 173–181

[23] M. Möhle, “Asymptotic results for coalescent processes without proper frequencies and applications to the two-parameter Poisson-Dirichlet coalescent”, Stoch. Process. Appl., 120 (2010), 2159–2173

[24] R. Neininger, L. Rüschendorf, “On the contraction method with degenerate limit equation”, Ann. Probab., 32 (2004), 2838–2856

[25] A. Panholzer, “Destruction of recursive trees”, Mathematics and Computer Science III, Birkhäuser, Basel, 2004, 267–280

[26] A. Panholzer, “Cutting down very simple trees”, Quaest. Math., 29 (2006), 211–227

[27] U. Rösler, “A limit theorem for “Quicksort””, RAIRO, Inform. Theor. Appl., 25 (1991), 85–100

[28] U. Rösler, “On the analysis of stochastic divide and conquer algorithms”, Algorithmica, 29 (2001), 238–261

[29] S. Sagitov, “Convergence to the coalescent with simultaneous multiple merges”, J. Appl. Prob., 40 (2003), 839–854

[30] R. Sedgewick, “The analysis of Quicksort Programs”, Acta Informatika, 7(4) (1977), 327–355