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

DOI10.1007/s00026-009-0007-zzbMath1232.60011arXivmath/0701288OpenAlexW2019666265MaRDI QIDQ659768

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)

Related Items

The uncover process for random labeled trees, Interval graph limits

Cites Work

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