Occurrence of patterns in random fields

we study the distribution of the occurrence of patterns in random fields on the lattice Zd , d >_ 2. The knowledge of such distributions is essential for the analysis of lossy and lossless compression schemes of multidimensional arrays. For 1-dimensional mixing processes a distribution of occurrence time t(An) of a pattern An, properly renormalised, converges to an exponential distribution. We generalize this result to higher dimensions. The main difficulty lies in the fact that mixing properties of random fields (d >_ 2) are very different from those of random processes (d = 1). We show that the mixing properties of Gibbsian (and hence Markov) random fields are sufficient for the convergence to the exponential law. As a corollary, we derive other probabilistic results for the distribution of t(An): the central limit theorem and the large deviation principle. Exponential law is also derived for the ¯rst occurrence of an approximate match for the pattern An.