32 Pages
English

Sharp Tail Bounds for Functionals of Markov Chains

-

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur
Sharp Tail Bounds for Functionals of Markov Chains – Journees de Probabilite - Lille 2008 Stephan Clemenc¸on Telecom ParisTech - LTCI UMR CNRS/Telecom ParisTech No 5141 Joint work with Patrice Bertail (Modal'x - Universite Paris X) Stephan Clemenc¸on (LTCI) Tail bounds for Markov chains 05/09/2008 1 / 21

  • ltci umr

  • mx n?2

  • journees de probabilite - lille

  • markov chain theory

  • instantaneous functionals

  • markov chains


Subjects

Informations

Published by
Reads 7
Language English
e´hptSn(LTn¸co´emeanClrofsdnuobliaT)IC/005nsaichovrkMa209/1/08
Sharp Tail Bounds for Functionals of Markov Chains Journe´esdeProbabilit´e-Lille2008
21
JointworkwithPatriceBertail(Modalx-Universit´eParisX)
Ste´phanCle´men¸con
Telecom ParisTech -LTCI UMR CNRS/Telecom ParisTech No 5141
l´nChaepon¸cenemaT)ICTL(sdnuobliS´t
2
A little Markov chain theory Markov with regeneration times General Harris Markov chains
1
Overall purpose
3
Probabilistic study based on renewal theory Limit behavior First order results
forMarkovchains0/5902/00282/1
4
The regenerative method Sharper results Tail bounds through the regenerative approach
05/0ainsovchMark
whereH(x) = (1 +x) log(1 +x)x. (Fuk & Nagaev, ’71)Relaxing the boundedness constraint: M,x>0, P{XYix} ≤ +exp )nP{Y1>M}, nMnσ22MH(nMσ2xMi=1
withσ2M=E[Yi2I{|Yi| ≤M}]. Our goal:extension to instantaneous functionals of a Markov chain, i.e. Yi=f(Xi), by means of theregenerative method.
(Bennett, ’62)LetY1, . . . ,Yn such that r.v.’sbe i.i.d.E[Yi] = 0, E[Yi2] =σ2<and|Yi| ≤Ma.s. . P{i=nX1Yix} ≤expMnσ22H(Mnσx2),
12
Overall purpose
80/3/902tSe´hpcon¸LTn(Clanme´ednuorofsT)ICblia