Types of Markov Fields and Tilings - Publikacja - MOST Wiedzy


Types of Markov Fields and Tilings


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.


  • 2


  • 2

    Web of Science

  • 3


Autorzy (3)

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Publikacja w czasopiśmie
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
IEEE TRANSACTIONS ON INFORMATION THEORY nr 62, wydanie 8, strony 4361 - 4375,
ISSN: 0018-9448
Rok wydania:
Opis bibliograficzny:
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
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1109/tit.2016.2573834
Politechnika Gdańska

wyświetlono 24 razy

Publikacje, które mogą cię zainteresować

Meta Tagi