Hostname: page-component-7c8c6479df-p566r Total loading time: 0 Render date: 2024-03-28T05:17:50.352Z Has data issue: false hasContentIssue false

A Generalization of the Erdős–Turán Law for the Order of Random Permutation

Published online by Cambridge University Press:  03 July 2012

ALEXANDER GNEDIN
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: a.gnedin@qmul.ac.uk)
ALEXANDER IKSANOV
Affiliation:
Faculty of Cybernetics, Taras Shevchenko National University of Kiev, Kiev-01033, Ukraine (e-mail: iksan@univ.kiev.ua, marynych@unicyb.kiev.ua)
ALEXANDER MARYNYCH
Affiliation:
Faculty of Cybernetics, Taras Shevchenko National University of Kiev, Kiev-01033, Ukraine (e-mail: iksan@univ.kiev.ua, marynych@unicyb.kiev.ua)

Abstract

We consider random permutations derived by sampling from stick-breaking partitions of the unit interval. The cycle structure of such a permutation can be associated with the path of a decreasing Markov chain on n integers. Under certain assumptions on the stick-breaking factor we prove a central limit theorem for the logarithm of the order of the permutation, thus extending the classical Erdős–Turán law for the uniform permutations and its generalization for Ewens' permutations associated with sampling from the PD/GEM(θ)-distribution. Our approach is based on using perturbed random walks to obtain the limit laws for the sum of logarithms of the cycle lengths.

Keywords

Type
Paper
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Abramowitz, M. and Stegun, I. (1964) Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Dover.Google Scholar
[2]Apostol, T. M. (1976) Introduction to Analytic Number Theory, Springer.Google Scholar
[3]Arratia, R., Barbour, A. D. and Tavaré, S. (2003) Logarithmic Combinatorial Structures: A Probabilistic Approach, European Mathematical Society.CrossRefGoogle Scholar
[4]Arratia, R. and Tavaré, S. (1992) Limit theorems for combinatorial structures via discrete process approximations. Random Struct. Alg. 3 321345.CrossRefGoogle Scholar
[5]Babu, G. J. and Manstavičius, E. (2002) Limit processes with independent increments for the Ewens sampling formula. Ann. Inst. Statist. Math. 54 607620.CrossRefGoogle Scholar
[6]Betz, V., Ueltschi, D. and Velenik, Y. (2011) Random permutations with cycle weights. Ann. Appl. Probab. 21 312331.CrossRefGoogle Scholar
[7]Bingham, N.H. (1973) Maxima of sums of random variables and suprema of stable processes. Z. Wahrsch. Verw. Gebiete. 26 273296.CrossRefGoogle Scholar
[8]DeLaurentis, J. M. and Pittel, B. G. (1985) Random permutations and Brownian motion. Pacific J. Math. 119 287301.CrossRefGoogle Scholar
[9]Diaconis, P. (1988) Group Representations in Probability and Statistics, Vol. 11 of IMS Lecture Notes, Monograph Series, Institute of Mathematical Statistics.Google Scholar
[10]Erdős, P. and Turán, P. (1967) On some problems of statistical group theory III. Acta. Math. Acad. Sci. Hungar. 18 309320.CrossRefGoogle Scholar
[11]Gnedin, A. (2004) The Bernoulli sieve. Bernoulli 10 7996.CrossRefGoogle Scholar
[12]Gnedin, A. (2004) Three sampling formulas. Combin. Probab. Comput. 13 185193.CrossRefGoogle Scholar
[13]Gnedin, A. (2011) Coherent random permutations with biased record statistics. Discrete Math. 311 8091.CrossRefGoogle Scholar
[14]Gnedin, A., Haulk, C. and Pitman, J. (2010) Characterizations of exchangeable partitions and random discrete distributions by deletion properties. In Probability and Mathematical Genetics: Papers in Honour of Sir John Kingman, Vol. 378 of London Mathematical Society Lecture Notes Series, Cambridge University Press, pp. 264298.CrossRefGoogle Scholar
[15]Gnedin, A., Iksanov, A. and Marynych, A. (2010) Limit theorems for the number of occupied boxes in the Bernoulli sieve. Theory of Stochastic Processes 16 4457.Google Scholar
[16]Gnedin, A., Iksanov, A. and Marynych, A. (2010) The Bernoulli sieve: an overview. Discr. Math. Theoret. Comput. Sci. Proceedings Series, AM, 329342.CrossRefGoogle Scholar
[17]Gnedin, A., Iksanov, A., Negadajlov, P. and Roesler, U. (2009) The Bernoulli sieve revisited. Ann. Appl. Prob. 19 16341655.CrossRefGoogle Scholar
[18]Gnedin, A., Iksanov, A. and Roesler, U. (2008) Small parts in the Bernoulli sieve. Discr. Math. Theoret. Comput. Sci. Proceedings Series, AI, 239246.CrossRefGoogle Scholar
[19]Gnedin, A. and Olshanski, G. (2006) Coherent permutations with descent statistic and the boundary problem for the graph of zigzag diagrams. Intern. Math. Res. Not. # 51968.CrossRefGoogle Scholar
[20]Gnedin, A. and Pitman, J. (2005) Regenerative composition structures. Ann. Probab. 33 445479.CrossRefGoogle Scholar
[21]Iksanov, A. On the number of empty boxes in the Bernoulli sieve I. Stochastics, to appear.Google Scholar
[22]Iksanov, A. (2012) On the number of empty boxes in the Bernoulli sieve II. Stoch. Proc. Appl. 122 27012729.CrossRefGoogle Scholar
[23]Lukacs, E. (1970) Characteristic Functions, Griffin.Google Scholar
[24]Jacquet, P. and Szpankowski, W. (1999) Entropy computations via analytic de-Poissonization. IEEE Trans. Inform. Theory 45 10721081.CrossRefGoogle Scholar
[25]Manstavičius, E. (2009) An analytic method in probabilistic combinatorics. Osaka J. Math. 46 273290.Google Scholar
[26]Medvedev, Y. I. (1977) Separable statistics in a polynomial scheme II. Theory Probab. Appl. 22 607615.CrossRefGoogle Scholar
[27]Mirakhmedov, S. A. (1989) Randomized decomposable statistics in a generalized allocation scheme over a countable set of cells. Diskretnaya Matematika 1 4662.Google Scholar
[28]Negadailov, P. (2010) Limit theorems for random recurrences and renewal-type processes. PhD thesis, Utrecht University.Google Scholar
[29]Pitman, J. (2006) Combinatorial Stochastic Processes, Springer.Google Scholar