Hitting with Restart: A Reason for Sisyphus Labour

Abstract : Motivated by applications in telecommunications, computer science and physics, we consider a discrete-time Markov process with restart in the Borel state space. At each step the process either with a positive probability restarts from a given distribution, or with the complementary probability continues according to a Markov transition kernel. The main focus of the present work is the expectation of the hitting time (to a given target set) of the process with restart, for which we obtain the explicit formula. Observing that the process with restart is positive Harris recurrent, we obtain the expression of its unique invariant probability. Then we show the equivalence of the following statements: (a) the boundedness (with respect to the initial state) of the expectation of the hitting time; (b) the finiteness of the expectation of the hitting time for almost all the initial states with respect to the unique invariant probability; and (c) the target set is of positive measure with respect to the invariant probability. We illustrate our results with two examples in uncountable and countable state spaces.
Complete list of metadatas

https://hal.inria.fr/hal-01055893
Contributor : Konstantin Avrachenkov <>
Submitted on : Saturday, March 28, 2015 - 3:18:25 PM
Last modification on : Wednesday, June 26, 2019 - 11:58:11 AM
Long-term archiving on: Tuesday, April 18, 2017 - 2:37:31 AM

Files

RR-8581.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01055893, version 2
  • ARXIV : 1503.08548

Collections

Citation

Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang. Hitting with Restart: A Reason for Sisyphus Labour. [Research Report] RR-8581, Inria. 2015, pp.15. ⟨hal-01055893v2⟩

Share

Metrics

Record views

179

Files downloads

114