Block sizes in two families of random permutations

Irina Cristali, Vinit Ranjan, Jake Steinberg, Erin Beckman, Rick Durrett, Matthew Junge, James Nolen

Published 2017-08-18Version 1

An interval of integers $[1,n]$ is said to be a block in an infinite permutation if the permutation maps $[1,n]$ onto itself. We study the size of the smallest block in $\mathbf p$-biased permutations that were recently introduced by Pitman and Tang, and contrast their behavior with results of Basu and Bhatnagar on block sizes in Mallows($q$) permutations. When $\mathbf p = \text{geometric}(p)$ we show for an explicit constant $b\approx 1.1524$ that $p \log K \to b$ in contrast to $p \log K \to \pi^2/6$ for Mallows($1-p$) permutations. For $\mathbf p$ obtained through i.i.d. stick breaking we give a general upper bound on $\mathbf E K$. This includes the case of geometric($p$)- and GEM($\theta$)-biased permutations. The approach uses a recursive distributional equation which, in principle, could be used to get very precise results about $\mathbf E K$.