Tight Markov chains and random compositions

Details Tight Markov chains and random compositions Tight Markov chains and random compositions

2010-05-11

arxiv.org/abs/1005.1957v1

Mathematics

Combinatorics

Scientific paper

For an ergodic Markov chain $\{X(t)\}$ on $\Bbb N$, with a stationary distribution $\pi$, let $T_n>0$ denote a hitting time for $[n]^c$, and let $X_n=X(T_n)$. Around 2005 Guy Louchard popularized a conjecture that, for $n\to \infty$, $T_n$ is almost Geometric($p$), $p=\pi([n]^c)$, $X_n$ is almost stationarily distributed on $[n]^c$, and that $X_n$ and $T_n$ are almost independent, if $p(n):=\sup_ip(i,[n]^c)\to 0$ exponentially fast. For the chains with $p(n) \to 0$ however slowly, and with $\sup_{i,j}\,\|p(i,\cdot)-p(j,\cdot)\|_{TV}<1$, we show that Louchard's conjecture is indeed true even for the hits of an arbitrary $S_n\subset\Bbb N$ with $\pi(S_n)\to 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 $k\,\sup_ip(i,S_n)$, by a $k$-long sequence of independent copies of $(\ell_n,t_n)$, where $\ell_n= \text{Geometric}\,(\pi(S_n))$, $t_n$ is distributed stationarily on $S_n$, and $\ell_n$ is independent of $t_n$. 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 $\nu$, a column-convex animal (cca) composition and a Carlitz (C) composition. We show that this approximation is indeed very sharp for most of the parts of the random compositions. Combining the two approximations in a tandem, we are able to determine the limiting distributions of $\mu=o(\ln\nu)$ and $\mu=o(\nu^{1/2})$ largest parts of the random cca composition and the random C-composition, respectively. (Submitted to Annals of Probability in August, 2009.)

Affiliated with

Also associated with

No associations

Rating

Tight Markov chains and random compositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight Markov chains and random compositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight Markov chains and random compositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498540