"Everything should be made as simple as possible, but not simpler." - Albert Einstein

Seminar Announcement

Doeblin's ergodicity coefficient: lower-complexity approximation of occupancy distributions

Manuel Lladser, Department of Applied Mathematics, University of Colorado at Boulder

Monday, February 28, 2011

4:00 p.m., room 223, Weber Bldg

ABSTRACT

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.