[{"date_created":"2021-09-12T22:01:25Z","conference":{"end_date":"2021-07-02","location":"Rome, Italy","start_date":"2021-06-29","name":"LICS: Logic in Computer Science"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["978-1-6654-4896-3"],"issn":["1043-6871"],"eisbn":["978-1-6654-4895-6"]},"year":"2021","doi":"10.1109/LICS52264.2021.9470595","acknowledgement":"We are grateful to the anonymous reviewers of LICS 2021 and of a previous version of this paper for insightful comments that helped improving the presentation. This research was partially supported by the grant ERC CoG 863818 (ForM-SMArt).","keyword":["Computer science","Heuristic algorithms","Memory management","Automata","Markov processes","Probability distribution","Complexity theory"],"publication_status":"published","isi":1,"language":[{"iso":"eng"}],"type":"conference","title":"Stochastic processes with expected stopping time","project":[{"call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"main_file_link":[{"url":"https://arxiv.org/abs/2104.07278","open_access":"1"}],"oa_version":"Preprint","day":"07","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"external_id":{"isi":["000947350400036"],"arxiv":["2104.07278"]},"date_published":"2021-07-07T00:00:00Z","publication":"Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science","abstract":[{"lang":"eng","text":"Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs."}],"related_material":{"record":[{"id":"18630","relation":"later_version","status":"public"}]},"oa":1,"date_updated":"2025-09-08T14:54:13Z","_id":"10004","status":"public","department":[{"_id":"KrCh"}],"scopus_import":"1","arxiv":1,"citation":{"chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 1–13. Institute of Electrical and Electronics Engineers, 2021. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>.","ama":"Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In: <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Institute of Electrical and Electronics Engineers; 2021:1-13. doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>","ieee":"K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,” in <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Rome, Italy, 2021, pp. 1–13.","apa":"Chatterjee, K., &#38; Doyen, L. (2021). Stochastic processes with expected stopping time. In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 1–13). Rome, Italy: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Institute of Electrical and Electronics Engineers, 2021, pp. 1–13, doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>.","ista":"Chatterjee K, Doyen L. 2021. Stochastic processes with expected stopping time. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 1–13.","short":"K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, Institute of Electrical and Electronics Engineers, 2021, pp. 1–13."},"quality_controlled":"1","article_processing_charge":"No","ec_funded":1,"page":"1-13","month":"07","publisher":"Institute of Electrical and Electronics Engineers"}]