Counting records in a random, non-uniform, permutation

Abstract

Counting permutations of $[n]$ by the number of records, i.e. left-to-right maxima, is a classic problem in combinatorial enumeration. In the first volume of ``The Art of Computer Programming", Donald Knuth demonstrated its relevance for analysis of average case complexity of a basic algorithm for determining a maximum in a linear list of numbers. It is well known that the expected, and likely, number of those records in a {\it uniformly\/} random permutation is asymptotic to $\log n$. Cyril Banderier, Rene Beier, and Kurt Mehlhorn studied the case of a non-uniform random permutation, which is obtained from a generic permutation of $[n]$ by selecting its elements one after another independently with probability $p$, and permuting the selected elements uniformly at random. They proved that $E_n(p)$, the largest expected number of the maxima, is between $\text{const}\sqrt{n/p}$ and $O\left(\sqrt{(n/p)\log n}\right)$ if $p$ is fixed. For $p\gg 1/n$ and simultaneously $1-p\ge \text{const }{n}^{-1/2}\log n$, we prove that $E_n(p)$ is exactly of order $(1-p)\sqrt{n/p}$.