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.
|Title of host publication||Proceedings of the 25th Symposium on Information Theory in the Benelux (Kerkrade, The Netherlands, June 2-4, 2004)|
|Place of Publication||Eindhoven, The Netherlands|
|Publisher||Werkgemeenschap voor Informatie- en Communicatietheorie (WIC)|
|Publication status||Published - 2004|
Chazottes, J. R., Redig, F. H. J., & Verbitskiy, E. A. (2004). Occurrence of patterns in random fields. In G. R. Pellikaan (Ed.), Proceedings of the 25th Symposium on Information Theory in the Benelux (Kerkrade, The Netherlands, June 2-4, 2004) (pp. 73-80). Werkgemeenschap voor Informatie- en Communicatietheorie (WIC).