UC Berkeley

We study the limiting behavior of Markov chains that iteratively generate a sequence of random finite words.

In the first part of thesis, we consider a Markov chain such that the $n^{\mathrm{th}}$ word is uniformly distributed over the set $\bW_n$ 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 also consider a Markov chain such that the $n^{\mathrm{th}}$ word takes values in the set of words in $\bB_n$ such that the number of letters $a$ in the first $k$ letters is at least the number of letters $b$ in those positions for any $1 \le k \le 2n$: at each step an $a$ and a $b$ are shuffled uniformly at random into the existing word so that the $a$ precedes the $b$. We obtain a concrete characterization of the respective Doob-Martin boundaries of these Markov chains and thereby delineate all the ways in which the Markov chains can be conditioned to behave at large times. We exhibit a bijective correspondence between the points in the respective boundaries of Markov chains and ergodic random total orders on the set $\{a_1, b_1, a_2, b_2, \ldots \}$ that have the specific properties determined by the Markov chains. We establish for the first Markov chain 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 $\frac{1}{2}(\mu+\nu)$ 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. $\nu$), 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$).

The second part of thesis focuses on the mixing time of a Markov chain of words in $\bW_n$ that arises from removing a letter $a$ and a letter $b$ uniformly at random followed by inserting the letter $a$ and the letter $b$ uniformly at random back into one of the slots defined by the remaining letters. We present an upper bound of the form $n \log n + (\log 8)n$ and a lower bound of the form $(1 - \alpha) n\log n - c_{\alpha} n, \alpha > \frac12$.