Types of markov fields and tilings

Yuliy Baryshnikov, Jaroslaw Jarek Duda, Wojciech Szpankowski

Research output: Contribution to journalArticle

Abstract

The method of types is one of the most popular techniques in information theory and combinatorics. However, thus far the method has been mostly applied to 1-D Markov processes, and it has not been thoroughly studied for general Markov fields. Markov fields over a finite alphabet of size $m\ge 2$ can be viewed as models for multidimensional systems with local interactions. The locality of these interactions is represented by a shape $\mathcal {S}$ while its marking by symbols of the underlying alphabet is called a tile. Two assignments in a Markov field have the same type if they have the same empirical distribution, i.e., if they have the same number of tiles of a given type. Our goal is to study the growth of the number of possible Markov field types in either a $d$ -dimensional box of lengths $n-{1}, \ldots , n-{d}$ or its cyclic counterpart, a $d$ -dimensional torus. We relate this question to the enumeration of nonnegative integer solutions of a large system of Diophantine linear equations called the conservation laws. We view a Markov type as a vector in a $D=m^{| {\mathcal {S}}|}$ dimensional space and count the number of such vectors satisfying the conservation laws, which turns out to be the number of integer points in a certain polytope. For the torus, this polytope is of dimension $\mu =D-1-\mathrm {rk}( {\mathrm {\mathrm{C}}})$ , where $\mathrm {rk( {\mathrm {\mathrm{C}}})}$ is the number of linearly independent conservation laws $ {\mathrm {\mathrm{C}}}$. This provides an upper bound on the number of types. Then, we construct a matching lower bound leading to the conclusion that the number of types in the torus Markov field is $\Theta (N^\mu )$ , where $N=n-{1}\ldots n-{d}$. These results are derived by geometric tools, including ideas of discrete and convex multidimensional geometry.

Original languageEnglish (US)
Article number7480427
Pages (from-to)4361-4375
Number of pages15
JournalIEEE Transactions on Information Theory
Volume62
Issue number8
DOIs
StatePublished - Aug 2016

Keywords

  • Markov fields
  • Markov types
  • analytic and discrete geometry
  • conservation laws
  • enumerative combinatorics
  • linear diophantine equations

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Types of markov fields and tilings'. Together they form a unique fingerprint.

  • Cite this