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

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 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)
Pages73-80
ISBN (Print)90-71048-20-9
Publication statusPublished - 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).