Markov field types and tilings

Yuliy Baryshnikov, Jaroslaw Duda, Wojciech Szpankowski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The method of types is one of the most popular technique in information theory and combinatorics. However, it was never thoroughly studied for Markov fields. Markov fields can be viewed as models for systems involving a large number of variables with local dependencies and interactions. These local dependencies can be captured by a shape of interactions (locations that contribute the next probability transition). Shapes marked by symbols from a finite alphabet are called tiles. Two assignments in a Markov filed have the same type if they have the same empirical distribution or they can be tiled by the same number of tile types. Our goal is to study the growth of the number of Markov field types or the number of tile types. This intricate and important problem was left open for too long.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2639-2643
Number of pages5
ISBN (Print)9781479951864
DOIs
StatePublished - Jan 1 2014
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2014 IEEE International Symposium on Information Theory, ISIT 2014
CountryUnited States
CityHonolulu, HI
Period6/29/147/4/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Markov field types and tilings'. Together they form a unique fingerprint.

  • Cite this

    Baryshnikov, Y., Duda, J., & Szpankowski, W. (2014). Markov field types and tilings. In 2014 IEEE International Symposium on Information Theory, ISIT 2014 (pp. 2639-2643). [6875312] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6875312