Block size in geometric(\(p\))-biased permutations. (English) Zbl 1398.05004

Summary: Fix a probability distribution \(\mathbf{p} = (p_1, p_2, \ldots)\) on the positive integers. The first block in a \(\mathfrak p\)-biased permutation can be visualized in terms of raindrops that land at each positive integer \(j\) with probability \(p_j\). It is the first point \(K\) so that all sites in \([1,K]\) are wet and all sites in \((K,\infty)\) are dry. For the geometric distribution \(p_j= p(1-p)^{j-1}\) we show that \(p \log K\) converges in probability to an explicit constant as \(p\) tends to 0. Additionally, we prove that if \(\mathfrak p\) has a stretch exponential distribution, then \(K\) is infinite with positive probability.


05A05 Permutations, words, matrices
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60K05 Renewal theory
Full Text: DOI arXiv Euclid


[1] A. D. Barbour, L. Holst, and S. Janson, Poisson approximation, Oxford science publications, Clarendon Press, 1992. · Zbl 0746.60002
[2] Riddhipratim Basu and Nayantara Bhatnagar, Limit theorems for longest monotone subsequences in random Mallows permutations, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 53 (2017), no. 4, 1934–1951. · Zbl 1382.60018 · doi:10.1214/16-AIHP777
[3] J. Duchamps, J. Pitman, and W. Tang, Renewal sequences and record chains related to multiple zeta sums, ArXiv e-prints (2017), To appear in Transactions of the American Mathematical Society.
[4] James Allen Fill, Hosam M. Mahmoud, and Wojciech Szpankowski, On the distribution for the duration of a randomized leader election algorithm, The Annals of Applied Probability 6 (1996), no. 4, 1260–1283. · Zbl 0870.60018 · doi:10.1214/aoap/1035463332
[5] Alexander Gnedin, Alexander Iksanov, and Alexander Marynych, Limit theorems for the number of occupied boxes in the Bernoulli sieve, 16 (2010). · Zbl 1249.60029
[6] Alexander Gnedin, Alexander Iksanov, and Alexander Marynych, A generalization of the Erdős–Turán law for the order of random permutation, Combinatorics, Probability and Computing 21 (2012), no. 5, 715–733. · Zbl 1248.60014 · doi:10.1017/S0963548312000247
[7] Alexander Gnedin and Grigori Olshanski, \(q\)-Exchangeability via quasi-invariance, The Annals of Probability (2010), 2103–2135. · Zbl 1204.60029 · doi:10.1214/10-AOP536
[8] Alexander V Gnedin et al., The Bernoulli sieve, Bernoulli 10 (2004), no. 1, 79–96. · Zbl 1044.60005
[9] Alexander V Gnedin, Alexander M Iksanov, Pavlo Negadajlov, Uwe Rösler, et al., The Bernoulli sieve revisited, The Annals of Applied Probability 19 (2009), no. 4, 1634–1655. · Zbl 1178.60019 · doi:10.1214/08-AAP592
[10] Svante Janson and Wojciech Szpankowski, Analysis of an asymmetric leader election algorithm, the electronic journal of combinatorics 4 (1997), no. 1, 17. · Zbl 0884.05004
[11] Alexander Marynych, Alexander Iksanov, and Alexander Gnedin, The Bernoulli sieve: an overview, Discrete Mathematics & Theoretical Computer Science (2010). · Zbl 1357.60026
[12] Jim Pitman and Wenpin Tang, Regenerative random permutations of integers, ArXiv e-prints: 1704.01166 (2017), To appear in Annals of Probability.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.