Deviation matrix in denumerable Markov processes: Characterisation, rank-one perturbation and restart

The Annals of Applied Probability, vol. 35, pp. 4354–4380

Abstract

We study the deviation matrix of denumerable state space, multi-chain Markov processes in continuous time. The deviation matrix is a measure of the cumulative deviation from the limiting probabilities and it plays an important role in many application domains. First, we provide several equivalent necessary and sufficient conditions for the existence of the deviation matrix. Next, we study a relation between the deviation matrix and rank-one perturbations of Markov processes. Based on a rank-one perturbation, we derive a versatile formula for the deviation matrix and apply this formula to Markov processes with restart. On the way, we needed to establish several new properties of rank-one perturbed Markov processes. We feel that those properties can be useful in their own right.

Authors 1

1. Konstantin E. Avrachenkov

   Institut national de recherche en sciences et technologies du numérique · NEO: Ingénierie et Opérations des Réseaux

   Affiliation as printed

   NEO team, Inria Sophia Antipolis