### Abstract

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.

Original language | English |
---|---|

Title of host publication | Proceedings of the 25th Symposium on Information Theory in the Benelux (Kerkrade, The Netherlands, June 2-4, 2004) |

Editors | G.R. Pellikaan |

Place of Publication | Eindhoven, The Netherlands |

Publisher | Werkgemeenschap voor Informatie- en Communicatietheorie (WIC) |

Pages | 73-80 |

ISBN (Print) | 90-71048-20-9 |

Publication status | Published - 2004 |

## Fingerprint Dive into the research topics of 'Occurrence of patterns in random fields'. Together they form a unique fingerprint.

## Cite this

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).