Types of Markov Fields and Tilings

Yuliy M. Baryshnikov, Jaroslaw Jarek Duda, Wojciech Szpankowski

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 ≥ 2 can be viewed as models for multidimensional systems with local interactions. The locality of these interactions is represented by a shape 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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , .. . ,n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sub> 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 = <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sub> |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 μ = D - 1 - rk(C), where rk(C) is the number of linearly independent conservation laws 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 θ(Nμ), where N = n <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> . . . nd. These results are derived by geometric tools, including ideas of discrete and convex multidimensional geometry.
BibTeX
@article{baryshnikov2016types,
  author = {Yuliy M. Baryshnikov and Jaroslaw Jarek Duda and Wojciech Szpankowski},
  title = {{Types of Markov Fields and Tilings}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  doi = {10.1109/tit.2016.2573834},
}

Loading related content...

Figure