Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T07:04:02.771Z Has data issue: false hasContentIssue false
  • English
  • Français

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 ,
ALEXANDER IKSANOV  and
ALEXANDER MARYNYCH
ALEXANDER GNEDIN
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: [email protected])
ALEXANDER IKSANOV
Affiliation:
Faculty of Cybernetics, Taras Shevchenko National University of Kiev, Kiev-01033, Ukraine (e-mail: [email protected], [email protected])
ALEXANDER MARYNYCH
Affiliation:
Faculty of Cybernetics, Taras Shevchenko National University of Kiev, Kiev-01033, Ukraine (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

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

Primary 60C05
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 5 , September 2012 , pp. 715 - 733
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 321–345.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 607–620.CrossRefGoogle Scholar
[6]Betz, V., Ueltschi, D. and Velenik, Y. (2011) Random permutations with cycle weights. Ann. Appl. Probab. 21 312–331.CrossRefGoogle Scholar
[7]Bingham, N.H. (1973) Maxima of sums of random variables and suprema of stable processes. Z. Wahrsch. Verw. Gebiete. 26 273–296.CrossRefGoogle Scholar
[8]DeLaurentis, J. M. and Pittel, B. G. (1985) Random permutations and Brownian motion. Pacific J. Math. 119 287–301.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 309–320.CrossRefGoogle Scholar
[11]Gnedin, A. (2004) The Bernoulli sieve. Bernoulli 10 79–96.CrossRefGoogle Scholar
[12]Gnedin, A. (2004) Three sampling formulas. Combin. Probab. Comput. 13 185–193.CrossRefGoogle Scholar
[13]Gnedin, A. (2011) Coherent random permutations with biased record statistics. Discrete Math. 311 80–91.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. 264–298.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 44–57.Google Scholar
[16]Gnedin, A., Iksanov, A. and Marynych, A. (2010) The Bernoulli sieve: an overview. Discr. Math. Theoret. Comput. Sci. Proceedings Series, AM, 329–342.CrossRefGoogle Scholar
[17]Gnedin, A., Iksanov, A., Negadajlov, P. and Roesler, U. (2009) The Bernoulli sieve revisited. Ann. Appl. Prob. 19 1634–1655.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, 239–246.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 445–479.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 2701–2729.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 1072–1081.CrossRefGoogle Scholar
[25]Manstavičius, E. (2009) An analytic method in probabilistic combinatorics. Osaka J. Math. 46 273–290.Google Scholar
[26]Medvedev, Y. I. (1977) Separable statistics in a polynomial scheme II. Theory Probab. Appl. 22 607–615.CrossRefGoogle Scholar
[27]Mirakhmedov, S. A. (1989) Randomized decomposable statistics in a generalized allocation scheme over a countable set of cells. Diskretnaya Matematika 1 46–62.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