Wyszukiwarka
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 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.
Cytowania
-
2
CrossRef
-
0
Web of Science
-
3
Scopus
Autorzy (3)
-
Yuliy Baryshnikov
- University of Illinois .
-
Jarosław Duda
- Uniwersytet Jagiellański .
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1109/TIT.2016.2573834
- Licencja
- Copyright (2016 IEEE)
Słowa kluczowe
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 94 razy