Compound Poisson Approximation for Markov Chains using Stein’s Method

Let $\eta$ be a stationary Harris recurrent Markov chain on a Polish state space $(S, \mathscr{F})$, with stationary distribution $\mu$. Let $\Psi_n:=\sum_{i-1}^n I\{\mu\in S_1\}$ be the number of visits to $S_1\in\mathscr{F}$ by $\eta$, where $S_1$ is “rare” in the sense that $\mu(S_1)$ is “small.” We want to find an approximating compound Poisson distribution for$ \mathscr{L}(\Psi_n)$, such that the approximation error, measured using the total variation distance, can be explicitly bounded with a bound of order not much larger than $\mu(S_1)$. This is motivated by the observation that approximating Poisson distributions often give larger approximation errors when the visits to $S_1$ by $\eta$ tend to occur in clumps and also by the compound Poisson limit theorems of classical extreme value theory. We here propose an approximating compound Poisson distribution which in a natural way takes into account the regenerative properties of Harris recurrent Markov chains. A total variation distance error bound for this approximation is derived, using the compound Poisson Stein equation of Barbour, Chen and Loh and certain couplings. When the chain has an atom $S_0$ (e.g., a singleton) such that $\mu(S_0)>0$, the bound depends only on much studied quantities like hitting probabilities and expected hitting times, which satisfy Poisson’s equation. As “by-products” we also get upper and lower bounds for the error in the approximation with Poisson or normal distributions. The above results are illustrated by numerical evaluations of the error bound for some Markov chains on finite state spaces.