DOOB-MARTIN COMPACTIFICATION OF A MARKOV CHAIN FOR GROWING RANDOM WORDS SEQUENTIALLY.

We consider a Markov chain that iteratively generates a sequence of random finite words in such a way that the word is uniformly distributed over the set of words of length 2 in which letters are and letters are at each step an and a are shuffled in uniformly at random among the letters of the current word. We obtain a concrete characterization of the Doob-Martin boundary of this Markov chain and thereby delineate all the ways in which the Markov chain can be conditioned to behave at large times. Writing for the number of letters (equivalently, ) in the finite word , we show that a sequence ( ) of finite words converges to a point in the boundary if, for an arbitrary word there is convergence as tends to infinity of the probability that the selection of () letters and () letters uniformly at random from and maintaining their relative order results in . We exhibit a bijective correspondence between the points in the boundary and ergodic random total orders on the set {, , , , …} that have distributions which are separately invariant under finite permutations of the indices of the 's and those of the 's. We establish a further bijective correspondence between the set of such random total orders and the set of pairs (, ) of diffuse probability measures on [0,1] such that ½( + ) is Lebesgue measure: the restriction of the random total order to {, ,…, } is obtained by taking ,…, (resp. ,… , ) i.i.d. with common distribution (resp. ), letting (,…, ) be {, ,…, , } in increasing order, and declaring that the smallest element in the restricted total order is (resp. ) if = (resp. = ).