{
  "id": "1605.03512",
  "version": "v1",
  "published": "2016-05-11T16:57:50.000Z",
  "updated": "2016-05-11T16:57:50.000Z",
  "title": "Doob-Martin compactification of a Markov chain for growing random words sequentially",
  "authors": [
    "Hye Soo Choi",
    "Steven N. Evans"
  ],
  "comment": "25 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-11T16:57:50.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "60J10",
      "68R15"
    ],
    "keywords": [
      "markov chain",
      "growing random words",
      "doob-martin compactification",
      "ergodic random total orders",
      "random finite words"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}