Tight Markov chains and random compositions

DOI10.1214/11-AOP656zbMATH Open1257.05009arXiv1005.1957OpenAlexW2963390441MaRDI QIDQ439877FDOQ439877

Authors: Boris Pittel 

Publication date: 17 August 2012

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: For an ergodic Markov chain $X(t)$ on $BbbN$, 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 $noinfty$, $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):=su{p}_{i}p(i,[n{]}^c)o0$ exponentially fast. For the chains with $p(n)o0$ however slowly, and with $su{p}_{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}subsetBbbN$ with $pi(S_n)o0$. 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,su{p}_{i}p(i,S_n)$, by a $k$-long sequence of independent copies of $(el{l}_n,t_n)$, where $el{l}_n=extGeometric,(pi(S_n))$, $t_n$ is distributed stationarily on $S_n$, and $el{l}_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 $u$, 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(lnu)$ and $mu=o(u^{1/2})$ largest parts of the random cca composition and the random C-composition, respectively. (Submitted to Annals of Probability in August, 2009.)

Full work available at URL: https://arxiv.org/abs/1005.1957

Recommendations

• Composition Markov chains of multinomial type
• scientific article; zbMATH DE number 1753163
• On Kendall's ‘Germ’ Conjecture for Markov Chains
• Approximating kth-order two-state Markov chains
• scientific article; zbMATH DE number 5200722

zbMATH Keywords

Markov chainsrandom compositions

Mathematics Subject Classification ID

Extreme value theory; extremal stochastic processes (60G70) Central limit and other weak theorems (60F05) Exact enumeration problems, generating functions (05A15) Discrete-time Markov processes on general state spaces (60J05) Combinatorial probability (60C05) Combinatorial aspects of partitions of integers (05A17) Additive number theory; partitions (11P99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the notion of recurrence in discrete stochastic processes
• Markov chain models - rarity and exponentiality
• Central and local limit theorems applied to asymptotic enumeration
• Title not available (Why is that?)
• Inequalities for rare events in time-reversible Markov chains. II
• On Carlitz compositions
• Markov chains with almost exponential hitting times
• A Solution to a Set of Fundamental Equations in Markov Chains
• Distinctness of compositions of an integer: A probabilistic analysis
• Title not available (Why is that?)
• Locally restricted compositions. I. Restricted adjacent differences
• Title not available (Why is that?)
• Probabilistic analysis of column-convex and directed diagonally-convex animals
• Title not available (Why is that?)
• On the Multiplicity of Parts in a Random Composition of a Large Integer
• Title not available (Why is that?)
• Stable husbands

Cited In (5)

• Combinatorial Markov chains on linear extensions
• Title not available (Why is that?)
• Precise asymptotics of some meeting times arising from the voter model on large random regular graphs
• Title not available (Why is that?)
• Composition Markov chains of multinomial type

This page was built for publication: Tight Markov chains and random compositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439877)