Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 8 Juin 2010

Doeblin's coefficient and occupancy distributions

par Manuel Lladser (U. Colorado)

We illustrate how a strictly positive Doeblin's coefficient leads to low- to moderate-complexity approximations of occupancy distributions of homogeneous Markov chains over finite state spaces, in the regime where exact calculations are impractical and asymptotic approximations may not be yet reliable. The key idea is to use Doeblin's coefficient to approximate a Markov chain of duration n by independent realizations of an auxiliary chain of duration O(ln(n)). To address the general case of an irreducible and aperiodic chain with a vanishing Doeblin's coefficient, we prove that Doeblin's coefficient satisfies a sub-multiplicative type inequality. A byproduct of this inequality is a new an elementary proof of Doeblin's characterization of the weak-ergodicity of non-homogeneous Markov chains.

This research has been partially supported by NSF grant DMS #0805950.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30