Analysis of Algorithms for Permutations Biased by Their Number of\n Records

2016/05/10 by Nicolas Auger, Mathilde Bouvel, Auger, Nicolas +5
Computer Science · Biochemistry, Genetics and Molecular Biology · #Bayesian Methods and Mixture Models #Genome Rearrangement Algorithms #Coding theory and cryptography

paper · pdf · doi:10.48550/arxiv.1605.02905

Abstract

The topic of the article is the parametric study of the complexity of\nalgorithms on arrays of pairwise distinct integers. We introduce a model that\ntakes into account the non-uniformness of data, which we call the Ewens-like\ndistribution of parameter \θ for records on permutations: the weight\n\θ^r of a permutation depends on its number r of records. We show that\nthis model is meaningful for the notion of presortedness, while still being\nmathematically tractable. Our results describe the expected value of several\nclassical permutation statistics in this model, and give the expected running\ntime of three algorithms: the Insertion Sort, and two variants of the Min-Max\nsearch.\n

Related

• Record-biased permutations and their permuton limit
• Counting records in a random, non-uniform, permutation
• Minimax Rates and Efficient Algorithms for Noisy Sorting
• Coherent random permutations with record statistics
• Mixing Times of Self-Organizing Lists and Biased Permutations