Markov field types and tilings

Yuliy Baryshnikov, Jaroslaw Duda, Wojciech Szpankowski

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


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
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781479951864
Publication statusPublished - Jan 1 2014
Externally publishedYes
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


Other2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/TerritoryUnited States
CityHonolulu, HI

All Science Journal Classification (ASJC) codes

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


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

Cite this