UC Berkeley

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 radix sort tree chains – the tree-valued Markov chains that arise when successively storing the finite collections of random infinite binary strings Z1,…,Zn, n = 1, 2,… according to the trie-based radix sort algorithm, where the source strings Z1, Z2,… are independent and identically distributed. We establish a bijective correspondence between the full Doob–Martin boundary of the radix sort tree chain with a symmetric Bernoulli source (that is, each Zk is a fair coin-tossing sequence) and the family of radix sort tree chains for which the common distribution of the Zk is a diffuse probability measure on {0, 1}∞. 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”.