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

Hye Soo Choi and Steven N. Evans

Stochastic Processes and their Applications, 2017, vol. 127, issue 7, 2428-2445

Abstract: We consider a Markov chain that iteratively generates a sequence of random finite words in such a way that the nth 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 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 N(u) for the number of letters a (equivalently, b) in the finite word u, we show that a sequence (un)n∈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 un 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 {a1,b1,a2,b2,…} 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 (μ,ν) of diffuse probability measures on [0,1] such that 12(μ+ν) is Lebesgue measure: the restriction of the random total order to {a1,b1,…,an,bn} is obtained by taking X1,…,Xn (resp. Y1,…,Yn) i.i.d. with common distribution μ (resp. ν), letting (Z1,…,Z2n) be {X1,Y1,…,Xn,Yn} in increasing order, and declaring that the kth smallest element in the restricted total order is ai (resp. bj) if Zk=Xi (resp. Zk=Yj).

Keywords: Harmonic function; Exchangeability; Bridge; Shuffle; Subword counting; Binomial coefficient; Plackett–Luce model; Vase model (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414916302162
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:127:y:2017:i:7:p:2428-2445

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2016.11.006

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().