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 : Wednesday, August 13, 2014 - 8:33:02 PM
Last modification on : Wednesday, June 26, 2019 - 11:58:11 AM
Long-term archiving on: Thursday, November 27, 2014 - 12:50:35 AM

Files

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

Identifiers

  • HAL Id : hal-01055893, version 1

Citation

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

Share

Metrics

Record views

322

Files downloads

106