DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2014.571

On the Complexity of Computing Maximum Entropy for Markovian Models

Authors: Taolue Chen and Tingting Han

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

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^CH_3 (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.

Cite as

Taolue Chen and Tingting Han. On the Complexity of Computing Maximum Entropy for Markovian Models. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 571-583, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.FSTTCS.2014.571,
  author =	{Chen, Taolue and Han, Tingting},
  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 =	{571--583},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.571},
  URN =		{urn:nbn:de:0030-drops-48725},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.571},
  annote =	{Keywords: Markovian Models, Entropy, Complexity, Probabilistic Verification}
}

Document

DOI: 10.4230/DagSemProc.07101.3

07101 Working Group Report – Performance Measures Other Than Time

Authors: Lucia Cloth, Pepijn Crouzen, Matthias Fruth, Tingting Han, David N. Jansen, Mark Kattenbelt, Gerard J. M. Smit, and Lijun Zhang

Published in: Dagstuhl Seminar Proceedings, Volume 7101, Quantitative Aspects of Embedded Systems (2007)

Abstract

This presentation shows a few possible performance measures that might be interesting and possible evaluation methods.

Cite as

Lucia Cloth, Pepijn Crouzen, Matthias Fruth, Tingting Han, David N. Jansen, Mark Kattenbelt, Gerard J. M. Smit, and Lijun Zhang. 07101 Working Group Report – Performance Measures Other Than Time. In Quantitative Aspects of Embedded Systems. Dagstuhl Seminar Proceedings, Volume 7101, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cloth_et_al:DagSemProc.07101.3,
  author =	{Cloth, Lucia and Crouzen, Pepijn and Fruth, Matthias and Han, Tingting and Jansen, David N. and Kattenbelt, Mark and Smit, Gerard J. M. and Zhang, Lijun},
  title =	{{07101 Working Group Report – Performance Measures Other Than Time}},
  booktitle =	{Quantitative Aspects of Embedded Systems},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7101},
  editor =	{Boudewijn Haverkort and Joost-Pieter Katoen and Lothar Thiele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07101.3},
  URN =		{urn:nbn:de:0030-drops-11396},
  doi =		{10.4230/DagSemProc.07101.3},
  annote =	{Keywords: }
}

Search Results

Documents authored by Han, Tingting

On the Complexity of Computing Maximum Entropy for Markovian Models

Abstract

Cite as

07101 Working Group Report – Performance Measures Other Than Time

Abstract

Cite as

Thanks for your feedback!

Could not send message