When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2021.5
URN: urn:nbn:de:0030-drops-143824
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14382/
 Go to the corresponding LIPIcs Volume Portal

### Enforcing ω-Regular Properties in Markov Chains by Restarting

 pdf-format:

### Abstract

Restarts are used in many computer systems to improve performance. Examples include reloading a webpage, reissuing a request, or restarting a randomized search. The design of restart strategies has been extensively studied by the performance evaluation community. In this paper, we address the problem of designing universal restart strategies, valid for arbitrary finite-state Markov chains, that enforce a given ω-regular property while not knowing the chain. A strategy enforces a property φ if, with probability 1, the number of restarts is finite, and the run of the Markov chain after the last restart satisfies φ. We design a simple "cautious" strategy that solves the problem, and a more sophisticated "bold" strategy with an almost optimal number of restarts.

### BibTeX - Entry

@InProceedings{esparza_et_al:LIPIcs.CONCUR.2021.5,
author =	{Esparza, Javier and Kiefer, Stefan and K\v{r}et{\'\i}nsk\'{y}, Jan and Weininger, Maximilian},
title =	{{Enforcing \omega-Regular Properties in Markov Chains by Restarting}},
booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
pages =	{5:1--5:22},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-203-7},
ISSN =	{1868-8969},
year =	{2021},
volume =	{203},
}