2014/06/16 by Nicholas F. Travers, Travers, Nicholas F.
Computer Science · Engineering · Mathematics · #60 #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Mathematics #Probability (math.PR) #graph theory and CDMA systems #math.PR #msc:60
paper · pdf · doi:10.48550/arxiv.1406.3911
30 pages, no figures
arxiv created 2014/06/16 · openalex publication_date 2014/06/16 · arxiv updated 2014/06/17 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
A random n-permutation may be generated by sequentially removing random cards C1,...,Cn from an n-card deck D = \1,...,n\. The permutation σ is simply the sequence of cards in the order they are removed. This permutation is itself uniformly random, as long as each random card Ct is drawn uniformly from the remaining set at time t. We consider, here, a variant of this simple procedure in which one is given a choice between k random cards from the remaining set at each step, and selects the lowest numbered of these for removal. This induces a bias towards selecting lower numbered of the remaining cards at each step, and therefore leads to a final permutation which is more "ordered" than in the uniform case (i.e. closer to the identity permutation id =(1,2,3,...,n)). We quantify this effect in terms of two natural measures of order: The number of inversions I and the length of the longest increasing subsequence L. For inversions, we establish a weak law of large numbers and central limit theorem, both for fixed and growing k. For the longest increasing subsequence, we establish the rate of scaling, in general, and existence of a weak law in the case of growing k. We also show that the minimum strategy, of selecting the minimum of the k given choices at each step, is optimal for minimizing the number of inversions in the space of all online k-card selection rules.