conference paper published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Manas Joglekar author Nisarg Shah author KrCh department FSTTCS: Foundations of Software Technology and Theoretical Computer Science Modern Graph Algorithmic Techniques in Formal Verification project Game Theory project Quantitative Graph Games: Theory and Applications project Microsoft Research Faculty Fellowship project We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning vertices from where the objective can be ensured with probability 1. We study for the first time the average case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average case running time is linear (as compared to the worst case linear number of iterations and quadratic time complexity). Second, for the average case analysis over all MDPs we show that the expected number of iterations is constant and the average case running time is linear (again as compared to the worst case linear number of iterations and quadratic time complexity). Finally we also show that given that all MDPs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small. https://research-explorer.ista.ac.at/download/2715/5040/IST-2016-525-v1+1_42_1_.pdf application/pdfno Schloss Dagstuhl - Leibniz-Zentrum für Informatik2012Hyderabad, India eng 10.4230/LIPIcs.FSTTCS.2012.461 18461 - 473 https://research-explorer.ista.ac.at/record/1598 Chatterjee, K., Joglekar, M., &#38; Shah, N. (2012). Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives (Vol. 18, pp. 461–473). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461">https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461</a> K. Chatterjee, M. Joglekar, and N. Shah, “Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Hyderabad, India, 2012, vol. 18, pp. 461–473. Chatterjee K, Joglekar M, Shah N. 2012. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 18, 461–473. Chatterjee, Krishnendu, Manas Joglekar, and Nisarg Shah. “Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives,” 18:461–73. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461">https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461</a>. Chatterjee, Krishnendu, et al. <i>Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives</i>. Vol. 18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–73, doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461">10.4230/LIPIcs.FSTTCS.2012.461</a>. Chatterjee K, Joglekar M, Shah N. Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives. In: Vol 18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:461-473. doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2012.461">10.4230/LIPIcs.FSTTCS.2012.461</a> K. Chatterjee, M. Joglekar, N. Shah, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 461–473. 27152018-12-11T11:59:13Z2025-09-23T08:00:31Z