Chernoff-type bound for finite Markov chains - ENAC - École nationale de l'aviation civile Accéder directement au contenu
Article Dans Une Revue The Annals of Applied Probability Année : 1998

Chernoff-type bound for finite Markov chains

Pascal Lezaud

Résumé

This paper develops bounds on the distribution function of the empirical mean for irreducible finite-state Markov chains. One approach, explored by D. Gillman, reduces this problem to bounding the largest eigenvalue of a perturbation of the transition matrix for the Markov chain. By using estimates on eigenvalues given in Kato's book ''Perturbation Theory for Linear Operators'', we simplify the proof of D. Gillman and extend it to non-reversible finite-state Markov chains and continuous time. We also set out another method, directly applicable to some general ergodic Markov kernels having a spectral gap.
Fichier principal
Vignette du fichier
437.pdf (147.43 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-00940907 , version 1 (01-04-2014)

Identifiants

  • HAL Id : hal-00940907 , version 1

Citer

Pascal Lezaud. Chernoff-type bound for finite Markov chains. The Annals of Applied Probability, 1998, 8 (3), pp 849-867. ⟨hal-00940907⟩

Collections

ENAC INSMI DGAC
150 Consultations
579 Téléchargements

Partager

Gmail Facebook X LinkedIn More