On the complexity of computing maximum entropy for Markovian models

Conference paper


Chen, T. and Han, T. 2014. On the complexity of computing maximum entropy for Markovian models. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014. New Delhi, India 15 - 17 Dec 2014 Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. pp. 571-583
TypeConference paper
TitleOn the complexity of computing maximum entropy for Markovian models
AuthorsChen, T. and Han, T.
Abstract

We investigate the complexity of computing entropy of various Markovian models including Markov Chains (MCs), Interval Markov Chains (IMCs) and Markov Decision Processes (MDPs). We consider both entropy and entropy rate for general MCs, and study two algorithmic questions, i.e., entropy approximation problem and entropy threshold problem. The former asks for an approximation of the entropy/entropy rate within a given precision, whereas the latter aims to decide whether they exceed a given threshold. We give polynomial-time algorithms for the approximation problem, and show the threshold problem is in P CH3 (hence in PSPACE) and in P assuming some number-theoretic conjectures. Furthermore, we study both questions for IMCs and MDPs where we aim to maximise the entropy/entropy rate among an infinite family of MCs associated with the given model. We give various conditional decidability results for the threshold problem, and show the approximation problem is solvable in polynomial-time via convex programming

KeywordsMarkovian Models, Entropy, Complexity, Probabilistic Verification
Research GroupFoundations of Computing group
Conference34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014
Page range571-583
ISSN1868-8969
ISBN
Hardcover9783939897774
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Publication dates
Print2014
Publication process dates
Deposited03 Jun 2015
Output statusPublished
Publisher's version
License
Web address (URL)http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.571
LanguageEnglish
Book title34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Permalink -

https://repository.mdx.ac.uk/item/85896

Download files


Publisher's version
  • 18
    total views
  • 1
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as