Non-asymptotic approximations in computational biology via maximal couplings
,Ìý
Date and time:Â
Friday, March 6, 2015 - 3:00pm
³¢´Ç³¦²¹³Ù¾±´Ç²Ô:Ìý
ECCR 265
´¡²ú²õ³Ù°ù²¹³¦³Ù:Ìý
In a report published in 1937, Doeblin - who is regarded the father of the "coupling method" - introduced an ergodicity coefficient that provided the first necessary and sufficient condition for the weak ergodicity of non-homogeneous Markov chains over finite state spaces. In today's jargon, this coefficient corresponds to the maximal coupling of the probability transition kernels associated with a Markov chain, and the Monte Carlo literature has (often implicitly) used it to draw perfectly from the stationary distribution of a homogeneous Markov chain over a Polish state space. Motivated by pattern problems in computational biology, in this talk I will show how Doeblin's ergodicity coefficient can be used to approximate the distribution of additive functionals of homogeneous Markov chains - rather than characterizing asymptotic objects such as stationary distributions. The proposed methodology (which is based on analytic combinatorics) leads to easy to compute and explicit error bounds in total variation distance, and may give access to approximations of additive functionals that are too long for exact calculation but also too short to rely on Normal approximations or stationary assumptions underlying Poisson approximations. This research was partially funded by the NSF DMS Grant #0805950.