Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence

DOI10.1007/S00026-009-0007-ZMaRDI QIDQ659768zbMATH OpenOpenAlexFDO

Authors Svante Janson

Publication date 24 January 2012

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0701288

zbMATH Keywords

Brownian motionrunspriority queuessorting algorithmevolution of random stringssock-sorting

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial probability (60C05)

Abstract: We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length n that starts as a string of 0's, and then evolves by changing each 0 to 1, with then changes done in random order. What is the maximal number of runs of 1's? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order n^{1/2}, and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to 1; there is also a second order term of order n^{1/3}. We also treat some variations, including priority queues. The proofs use methods originally developed for random graphs.

Recommendations

• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence: extended abstract.
• Random time changes for sock-sorting and other stochastic process limit theorems
• Randomized adaptive sorting
• Almost-sure asymptotics for the number of heaps inside a random sequence
• A limit theorem for “quicksort”

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 4034749 (Why is no real title available?)
• scientific article; zbMATH DE number 3484998 (Why is no real title available?)
• scientific article; zbMATH DE number 1149769 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• A functional limit theorem for random graphs with applications to subgraph count statistics
• Brownian motion and a sharply curved boundary
• DISTRIBUTION OF GROUPS IN A SEQUENCE OF ALTERNATIVES
• Data Structures' Maxima
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Large finite population queueing systems part i: the infinite server model.
• Maximum queue size and hashing with lazy deletion
• Orthogonal decompositions and functional limit theorems for random graph statistics
• Probability: A Graduate Course
• Random time changes for sock-sorting and other stochastic process limit theorems
• Random walks, Gaussian processes and list structures
• Sequence of operations analysis for dynamic data structures
• The Distribution Theory of Runs
• The analysis of simple list structures
• The complexity of hashing with lazy deletion
• The maximum of a Gaussian process whose mean path has a maximum, with an application to the strength of bundles of fibres
• The maximum of a random walk whose mean path has a maximum
• The maximum size of a closed epidemic

Cited in

(5)

• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence
• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence: extended abstract.
• The uncover process for random labeled trees
• scientific article; zbMATH DE number 1741785 (Why is no real title available?)
• Interval graph limits

This page was built for publication: Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659768)