## 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) |
---|---|

Article number | 7480427 |

Pages (from-to) | 4361-4375 |

Number of pages | 15 |

Journal | IEEE Transactions on Information Theory |

Volume | 62 |

Issue number | 8 |

DOIs | |

State | 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