## Compound Poisson approximation for Markov chains

Let be a stationary Harris recurrent Markov chain on a Polish state space , with stationary distribution . Let be the number of visits to by , where is "rare" in the sense that is "small". We want to find an approximating compound Poisson distribution for , such that the approximation error, measured using the total variation distance, can be explicitly bounded with a bound of order not much larger than . This is motivated by the observation that approximating Poisson distributions often give larger approximation errors when the visits to by 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 (1992), and certain couplings. When the chain has an atom (e.g., a singleton), the bound is particularly simple, and depends only on much studied quantities like hitting probabilities and expected hitting times, which satisfy Poisson's equation and can in some cases be bounded using Lyapunov functions. Adding a few terms to the bound gives upper and lower bounds for the error in the approximation with arbitrary compound Poisson, or normal, distributions. Applications of the above results are given, to the number of overlapping occurrences of fixed sequences in finite-state Markov chains (in particular, the sequence 111...111 in a Markov chain on ), and to the visits by birth-death chains and arbitrary finite-state Markov chains to "rare" sets.

The most important application concerns the Johnson-Mehl crystallization model of stochastic geometry. In this model, for each point of a Poisson point process on , an interval starts to grow in from with constant speed in both directions at time . Let be the number of components of the uncovered set (= the complement of the union of growing random intervals) which intersect , at time . can be interpreted as the number of visits to a "rare" set by a Markov chain. We first give an approximating Poisson distribution for , and a total variation distance error bound, using the Stein-Chen method and the existence of monotone increasing couplings. Then, using the general results described above and suitable couplings, we give an approximating compound Poisson distribution, and an error bound for this approximation. Under a mild condition, the latter bound is of considerably smaller order than the former. These results are illustrated numerically.

Keywords: Compound Poisson approximation, error bound, stationary Harris chain, "rare" set, Stein equation, coupling, expected hitting times, overlapping occurrences of patterns, Johnson-Mehl model, uncovered set.

AMS 1991 subject classification: Primary 60E15, 60J05. Secondary 60D05, 60G70.