Almost-sure asymptotics for the number of heaps inside a random sequence

[摘要] We study the minimum number of heaps required to sort a random sequence using a generalization of Istrate and Bonchis’s algorithm (2015). In a previous paper, the authors proved that the expected number of heaps grows logarithmically. In this note, we improve on the previous result by establishing the almost-sure and $L^1$ convergence.

[学科分类] 统计和概率

[关键词] Hammersley’s process;heap sorting;patience sorting;longest increasing subsequences;interacting particles systems;almost-sure convergence