Chen, Taolue ;
Han, Tingting
On the Complexity of Computing Maximum Entropy for Markovian Models
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 polynomialtime algorithms for the approximation problem, and show the threshold problem is in P^CH_3 (hence in PSPACE) and in P assuming some numbertheoretic 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 polynomialtime via convex programming.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2014:4872,
author = {Taolue Chen and Tingting Han},
title = {{On the Complexity of Computing Maximum Entropy for Markovian Models}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {571583},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897774},
ISSN = {18688969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4872},
URN = {urn:nbn:de:0030drops48725},
doi = {10.4230/LIPIcs.FSTTCS.2014.571},
annote = {Keywords: Markovian Models, Entropy, Complexity, Probabilistic Verification}
}
2014
Keywords: 

Markovian Models, Entropy, Complexity, Probabilistic Verification 
Seminar: 

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Issue date: 

2014 
Date of publication: 

2014 