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. Writing $N(u)$ for the number of letters $a$ (equivalently, $b$) in the finite word $u$, we show that a sequence $(u_n)_{n in mathbb{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 selection of $N(v)$ letters $a$ and $N(v)$ letters $b$ uniformly at random from $u_n$ and maintaining their relative order 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, u)$ of diffuse probability measures on $[0,1]$ such that $frac{1}{2}(mu+ u)$ is Lebesgue measure: the restriction of the random total order to ${a_1, b_1, ldots, a_n, b_n}$ is obtained by taking $X_1, ldots, X_n$ (resp. $Y_1, ldots, Y_n$) i.i.d. with common distribution $mu$ (resp. $ u$), letting $(Z_1, ldots, Z_{2n})$ be ${X_1, Y_1, ldots, X_n, Y_n}$ in increasing order, and declaring that the $k^{mathrm{th}}$ smallest element in the restricted total order is $a_i$ (resp. $b_j$) if $Z_k = X_i$ (resp. $Z_k = Y_j$).
Download