 Main
The DoobMartin compactification of Markov chains of growing words
 Choi, Hye Soo
 Advisor(s): Evans, Steven N
Abstract
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 DoobMartin 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$.
Main Content
Enter the password to open this PDF file:













