Search
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)
-
Yuliy Baryshnikov
- University of Illinois .
-
Jarosław Duda
- Uniwersytet Jagiellański .
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1109/TIT.2016.2573834
- License
- Copyright (2016 IEEE)
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 130 times