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

Autorzy (3)

• 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