Document Open Access Logo

On the Complexity of Computing Maximum Entropy for Markovian Models

Authors Taolue Chen, Tingting Han

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.571.pdf
  • Filesize: 458 kB
  • 13 pages

Document Identifiers

Author Details

Taolue Chen
Tingting Han

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.571

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.

Subject Classification

Keywords
  • Markovian Models
  • Entropy
  • Complexity
  • Probabilistic Verification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen. On the complexity of numerical analysis. SIAM J. Comput., 38(5):1987-2006, 2009. Google Scholar
  2. Nicolas Basset. A maximal entropy stochastic process for a timed automaton,. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, ICALP (2), volume 7966 of Lecture Notes in Computer Science, pages 61-73. Springer, 2013. Google Scholar
  3. Aharon Ben-Tal and Arkadi Nemirovski. Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. Society for Industrial and Applied Mathematics, 1987. Google Scholar
  4. Michael Benedikt, Rastislav Lenhardt, and James Worrell. Ltl model checking of interval markov chains. In Nir Piterman and Scott A. Smolka, editors, TACAS, volume 7795 of Lecture Notes in Computer Science, pages 32-46. Springer, 2013. Google Scholar
  5. Dimitri P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, 2011. Google Scholar
  6. Fabrizio Biondi, Axel Legay, Pasquale Malacaria, and Andrzej Wasowski. Quantifying information leakage of randomized protocols. In Roberto Giacobazzi, Josh Berdine, and Isabella Mastroeni, editors, VMCAI, volume 7737 of Lecture Notes in Computer Science, pages 68-87. Springer, 2013. Google Scholar
  7. Fabrizio Biondi, Axel Legay, Bo Friis Nielsen, and Andrzej Wasowski. Maximizing entropy over markov processes. In Adrian Horia Dediu, Carlos Martín-Vide, and Bianca Truthe, editors, LATA, volume 7810 of Lecture Notes in Computer Science, pages 128-140. Springer, 2013. Google Scholar
  8. Fabrizio Biondi, Axel Legay, Louis-Marie Traonouez, and Andrzej Wasowski. Quail: A quantitative security analyzer for imperative code. In Sharygina and Veith [28], pages 702-707. Google Scholar
  9. Michele Boreale. Quantifying information leakage in process calculi. Inf. Comput., 207(6):699-725, 2009. Google Scholar
  10. Richard P. Brent. Fast multiple-precision evaluation of elementary functions. J. ACM, 23(2):242-251, 1976. Google Scholar
  11. Pavol Cerný, Krishnendu Chatterjee, and Thomas A. Henzinger. The complexity of quantitative information flow problems. In CSF, pages 205-217. IEEE Computer Society, 2011. Google Scholar
  12. Rohit Chadha and Michael Ummels. The complexity of quantitative information flow in recursive programs. In Deepak D'Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors, FSTTCS, volume 18 of LIPIcs, pages 534-545. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. Google Scholar
  13. Krishnendu Chatterjee, Koushik Sen, and Thomas A. Henzinger. Model-checking omega-regular properties of interval Markov chains. In Roberto M. Amadio, editor, FoSSaCS, volume 4962 of Lecture Notes in Computer Science, pages 302-317. Springer, 2008. Google Scholar
  14. Taolue Chen and Tingting Han. On the complexity of computing maximum entropy for Markovian models. Technical report, Middlesex University London, 2014. Available via URL: http://www.cs.mdx.ac.uk/staffpages/taoluechen/pub-papers/fsttcs14-full.pdf.
  15. Taolue Chen, Tingting Han, and Marta Z. Kwiatkowska. On the complexity of model checking interval-valued discrete time markov chains. Inf. Process. Lett., 113(7):210-216, 2013. Google Scholar
  16. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley and Sons, Inc., New York, NY, USA, 1991. Google Scholar
  17. Luca de Alfaro. Computing minimum and maximum reachability times in probabilistic systems. In Jos C. M. Baeten and Sjouke Mauw, editors, CONCUR, volume 1664 of Lecture Notes in Computer Science, pages 66-81. Springer, 1999. Google Scholar
  18. Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis. A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing. TOCT, 6(2):9, 2014. Google Scholar
  19. Valerie Girardin. Entropy maximization for Markov and semi-Markov processes. Methodology and Computing in Appplied Probability, 6:109-127, 2004. Google Scholar
  20. Martin Grotschel, Laszlo Lovasz, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics. Springer-Verlag, 1987. Google Scholar
  21. John G. Kemeny and J. Snell. Finite Markov Chains. Undergraduate Texts in Mathematics. Springer-Verlag, 3rd printing 1983 edition edition, 1983. Google Scholar
  22. Igor Kozine and Lev V. Utkin. Interval-valued finite Markov chains. Reliable Computing, 8(2):97-113, 2002. Google Scholar
  23. A. J. Macintyre and A. J. Wilkie. On the decidability of the real exponential field. Odifreddi, P. G., Kreisel 70th Birthday Volume, CLSI, 1995. Google Scholar
  24. William Parry. Intrinsic markov chains. Trans. Amer. Math. Soc., 112:55-66, 1964. Google Scholar
  25. Alberto Puggelli, Wenchao Li, Alberto L. Sangiovanni-Vincentelli, and Sanjit A. Seshia. Polynomial-time verification of pctl properties of mdps with convex uncertainties. In Sharygina and Veith [28], pages 527-542. Google Scholar
  26. Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York, 1994. Google Scholar
  27. Koushik Sen, Mahesh Viswanathan, and Gul Agha. Model-checking Markov chains in the presence of uncertainties. In Holger Hermanns and Jens Palsberg, editors, TACAS, volume 3920 of Lecture Notes in Computer Science, pages 394-410. Springer, 2006. Google Scholar
  28. Natasha Sharygina and Helmut Veith, editors. Computer Aided Verification - 25th International Conference, CAV 2013, Saint Petersburg, Russia, July 13-19, 2013. Proceedings, volume 8044 of Lecture Notes in Computer Science. Springer, 2013. Google Scholar
  29. Alex J. Wilkie. Model completeness results for expansions of the ordered field of real numbers by restricted pfaffian functions and the exponential functions. J. Amer. Math. Soc., 9:1051–1094, 1996. Google Scholar
  30. Hirotoshi Yasuoka and Tachio Terauchi. Quantitative information flow - verification hardness and possibilities. In CSF, pages 15-27. IEEE Computer Society, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact