Occurrence of patterns in random fields

J.R. Chazottes, F.H.J. Redig, E.A. Verbitskiy

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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 languageEnglish
Title of host publicationProceedings of the 25th Symposium on Information Theory in the Benelux (Kerkrade, The Netherlands, June 2-4, 2004)
EditorsG.R. Pellikaan
Place of PublicationEindhoven, The Netherlands
PublisherWerkgemeenschap voor Informatie- en Communicatietheorie (WIC)
ISBN (Print)90-71048-20-9
Publication statusPublished - 2004


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

Cite this