Doob-Martin compactification of a Markov chain for growing random words sequentially

Hye Soo Choi, Steven N. Evans

Published 2016-05-11Version 1

We consider a Markov chain that iteratively generates a sequence of random finite words in such a way that the $n^{\mathrm{th}}$ word is uniformly distributed over the set of words of length $2n$ in which $n$ letters are $a$ and $n$ letters are $b$: at each step an $a$ and a $b$ 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 $|u|$ for the number of letters $a$ (equivalently, $b$) in the finite word $u$, we show that a sequence $(u_n)$ of finite words converges to a point in the boundary if, for an arbitrary word $v$, there is convergence as $n$ tends to infinity of the probability that the removal of $|u_n|-|v|$ letters $a$ and $|u_n|-|v|$ letters $b$ uniformly at random from $u_n$ results in $v$. We exhibit a bijective correspondence between the points in the boundary and ergodic random total orders on the set $\{a_1, b_1, a_2, b_2, \ldots \}$ that have distributions which are separately invariant under finite permutations of the indices of the $a'$s and those of the $b'$s. We establish a further bijective correspondence between the set of such random total orders and the set of pairs $(\mu,\nu)$ of diffuse probability measures on $[0,1]$ such that $(\mu+\nu)$/2 is Lebesgue measure.