# Types of markov fields and tilings

Yuliy Baryshnikov, Jaroslaw Jarek Duda, Wojciech Szpankowski

Research output: Contribution to journalArticlepeer-review

## 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 language English (US) 7480427 4361-4375 15 IEEE Transactions on Information Theory 62 8 https://doi.org/10.1109/TIT.2016.2573834 Published - 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.