Types of Markov Fields and Tilings - Publication - Bridge of Knowledge

Search

Types of Markov Fields and Tilings

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 one-dimensional 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 multi-dimensional 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 n1, ...,nd 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|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 = n1 ···nd. These results are derived by geometric tools including ideas of discrete and convex multidimensional geometry.

Citations

  • 2

    CrossRef

  • 0

    Web of Science

  • 3

    Scopus

Authors (3)

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:
Articles
Type:
artykuł w czasopiśmie wyróżnionym w JCR
Published in:
IEEE TRANSACTIONS ON INFORMATION THEORY no. 62, edition 8, pages 4361 - 4375,
ISSN: 0018-9448
Language:
English
Publication year:
2016
Bibliographic description:
Baryshnikov Y., Duda J., Szpankowski W.: Types of Markov Fields and Tilings // IEEE TRANSACTIONS ON INFORMATION THEORY. -Vol. 62, iss. 8 (2016), s.4361-4375
DOI:
Digital Object Identifier (open in new tab) 10.1109/tit.2016.2573834
Verified by:
Gdańsk University of Technology

seen 89 times

Recommended for you

Meta Tags