Tight Markov chains and random compositions
- Autores: Boris Pittel
- Localización: Annals of probability: An official journal of the Institute of Mathematical Statistics, ISSN 0091-1798, Vol. 40, Nº. 4, 2012, págs. 1535-1576
- Idioma: inglés
- DOI: 10.1214/11-AOP656
- Texto completo no disponible (Saber más ...)
-
Resumen
For an ergodic Markov chain {X(t)} on N, with a stationary distribution π, let Tn>0 denote a hitting time for [n]c, and let Xn=X(Tn). Around 2005 Guy Louchard popularized a conjecture that, for n→∞, Tn is almost Geometric(p), p=π([n]c), Xn is almost stationarily distributed on [n]c and that Xn and Tn are almost independent, if p(n):=supip(i,[n]c)→0 exponentially fast. For the chains with p(n)→0, however slowly, and with supi,j∥p(i,⋅)−p(j,⋅)∥TV<1, we show that Louchard’s conjecture is indeed true, even for the hits of an arbitrary Sn⊂N with π(Sn)→0. More precisely, a sequence of k consecutive hit locations paired with the time elapsed since a previous hit (for the first hit, since the starting moment) is approximated, within a total variation distance of order ksupip(i,Sn), by a k-long sequence of independent copies of (ℓn,tn), where tn=Geometric(π(Sn)), ℓn is distributed stationarily on Sn and ℓn is independent of tn. The two conditions are easily met by the Markov chains that arose in Louchard’s studies as likely sharp approximations of two random compositions of a large integer ν, a column-convex animal (cca) composition and a Carlitz (C) composition. We show that this approximation is indeed very sharp for each of the random compositions, read from left to right, for as long as the sum of the remaining parts stays above ln2ν. Combining the two approximations, a composition—by its chain, and, for Sn=[n]c, the sequence of hit locations paired each with a time elapsed from the previous hit—by the independent copies of (ℓn,tn), enables us to determine the limiting distributions of μ=o(lnν) and μ=o(ν1/2) largest parts of the random cca-composition and the random C-composition, respectively. (Submitted to Annals of Probability in June 2009.)
