Compound Poisson approximation for Markov chains

Let tex2html_wrap_inline37 be a stationary Harris recurrent Markov chain on a Polish state space tex2html_wrap_inline39 , with stationary distribution tex2html_wrap_inline41 . Let tex2html_wrap_inline43 be the number of visits to tex2html_wrap_inline45 by tex2html_wrap_inline37 , where tex2html_wrap_inline49 is "rare" in the sense that tex2html_wrap_inline51 is "small". We want to find an approximating compound Poisson distribution for tex2html_wrap_inline53 , such that the approximation error, measured using the total variation distance, can be explicitly bounded with a bound of order not much larger than tex2html_wrap_inline51 . This is motivated by the observation that approximating Poisson distributions often give larger approximation errors when the visits to tex2html_wrap_inline49 by tex2html_wrap_inline37 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 tex2html_wrap_inline63 ), 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 tex2html_wrap_inline65 of a Poisson point process on tex2html_wrap_inline67 , an interval starts to grow in tex2html_wrap_inline69 from tex2html_wrap_inline71 with constant speed in both directions at time tex2html_wrap_inline73 . Let tex2html_wrap_inline75 be the number of components of the uncovered set (= the complement of the union of growing random intervals) which intersect tex2html_wrap_inline77 , at time tex2html_wrap_inline79 . tex2html_wrap_inline75 can be interpreted as the number of visits to a "rare" set by a Markov chain. We first give an approximating Poisson distribution for tex2html_wrap_inline83 , 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.