# Types of Markov Fields and Tilings - Publikacja - MOST Wiedzy

## Types of Markov Fields and Tilings

### Abstrakt

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 ﬁelds. Markov ﬁelds over a ﬁnite 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 ﬁeld 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 ﬁeld 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 ﬁeld is Θ(Nµ) where N = n1 ···nd. These results are derived by geometric tools including ideas of discrete and convex multidimensional geometry.

### Cytowania

• 2

CrossRef

• 2

Web of Science

• 3

Scopus

• ### Yuliy Baryshnikov

• University of Illinois .
• ### Jarosław Duda

• Uniwersytet Jagiellański .

### Pełna treść

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

### Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
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
Język:
angielski
Rok wydania:
2016
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
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1109/tit.2016.2573834
Weryfikacja:
Politechnika Gdańska

wyświetlono 24 razy

2013

2013

2014

2021