Tight Markov chains and random compositions

DOI10.1214/11-AOP656MaRDI QIDQ439877zbMATH OpenOpenAlexFDO

Publication date 17 August 2012

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

Full work available at URL https://arxiv.org/abs/1005.1957, https://projecteuclid.org/euclid.aop/1341401143

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)

Abstract: For an ergodic Markov chain

X (t)

on

B b b N

, with a stationary distribution

p i

, 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 o i n f t y

,

T_{n}

is almost Geometric(

p

),

p = p i ([n]^{c})

,

X_{n}

is almost stationarily distributed on

[n]^{c}

, and that

X_{n}

and

T_{n}

are almost independent, if

p (n) := s u p_{i} p (i, [n]^{c}) o 0

exponentially fast. For the chains with

p (n) o 0

however slowly, and with

s u p_{i, j}, | p (i, c d o t) - p (j, c d o t) |_{T V} < 1

, we show that Louchard's conjecture is indeed true even for the hits of an arbitrary

S_{n} s u b s e t B b b N

with

p i (S_{n}) o 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, s u p_{i} p (i, S_{n})

, by a

k

-long sequence of independent copies of

(e l l_{n}, t_{n})

, where

e l l_{n} = e x t G e o m e t r i c, (p i (S_{n}))

,

t_{n}

is distributed stationarily on

S_{n}

, and

e l 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

m u = o (l n u)

and

m u = 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.)

Recommendations

Cites work

Cited in

(5)

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)