Radix sort trees in the large

DOI10.1214/17-ECP77MaRDI QIDQ1689831zbMATH OpenOpenAlexFDO

Authors Steven Neil Evans, Anton Wakolbinger

Publication date 18 January 2018

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.07385, https://projecteuclid.org/euclid.ecp/1512097482

zbMATH Keywords

exchangeabilityharmonic functionbridgebinary treeDoob-Martin kerneltail \(\sigma\)-field

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms (68W40) Boundary theory for Markov processes (60J50)

Abstract: The trie-based radix sort algorithm stores pairwise different infinite binary strings in the leaves of a binary tree in a way that the Ulam-Harris coding of each leaf equals a prefix (that is, an initial segment) of the corresponding string, with the prefixes being of minimal length so that they are pairwise different. We investigate the {em radix sort tree chains} -- the tree-valued Markov chains that arise when successively storing infinite binary strings $Z_1,ldots,Z_n$, $n=1,2,ldots$ according to the trie-based radix sort algorithm, where the source strings $Z_1,Z_2,ldots$ are independent and identically distributed. We establish a bijective correspondence between the full Doob--Martin boundary of the radix sort tree chain with a {em symmetric Bernoulli source} (that is, each $Z_k$ is a fair coin-tossing sequence) and the family of radix sort tree chains for which the common distribution of the $Z_k$ is a diffuse probability measure on ${0,1}^{i}nfty$. In essence, our result characterizes all the ways that it is possible to condition such a chain of radix sort trees consistently on its behavior "in the large".

Recommendations

• Radix sort on the hypercube
• Efficient multiway radix search trees
• Power balance and apportionment algorithms for the United States Congress
• Randomized binary search trees
• Randomized search trees
• scientific article; zbMATH DE number 1268192
• Breadth-first traversal of trees and integer sorting in parallel
• Computational Science – ICCS 2005
• scientific article; zbMATH DE number 1305510
• Ordering trees by their largest eigenvalues

Cited in

(3)

• General erased-word processes: product-type filtrations, ergodic laws and Martin boundaries
• Exchangeable interval hypergraphs and limits of ordered discrete structures
• PATRICIA bridges

This page was built for publication: Radix sort trees in the large

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