Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, September 21, 2010 - 4:00pm

Manuel Lladser

University of Colorado at Boulder

Location

University of Pennsylvania

DRL 4C6

Note time change - 30 minutes earlier than usual.

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.