Some tree-valued chains and their bridges
Steve Evans
We consider a number of Markov chains that take values in collections of finite rooted binary trees. Among these are R\'emy's chain for generating uniformly distributed finite rooted full binary trees and chains that arise by feeding a sequence of i.i.d. inputs into computer science algorithms such as binary sort, digital sort, radix sort, and PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric). We are interested in the ``infinite bridges'' of such highly transient chains; that is, very roughly speaking, how is it possible to condition such a process to behave at large times. This question is intimately tied up with the question of determining the Doob-Martin boundary or, equivalently, the class of positive harmonic functions for these chains. We will show, for example, that R\'emy's chain and the PATRICIA chains have the same bridges and the characterization of these bridges involves a detour through the world of real trees thought of as metric measure spaces.