A Scaling Analysis of a Cat and Mouse Markov Chain

Abstract : Motivated by an original on-line page-ranking algorithm, starting from an arbitrary Markov chain (C_n) on a discrete state space S, a Markov chain (C_n,M_n) on the product space S^2, the cat and mouse Markov chain, is constructed. The first coordinate of this Markov chain behaves like the original Markov chain and the second component changes only when both coordinates are equal. The asymptotic properties of this Markov chain are investigated. A representation of its invariant measure is in particular obtained. When the state space is infinite it is shown that this Markov chain is in fact null recurrent if the initial Markov chain (C_n) is positive recurrent and reversible. In this context, the scaling properties of the location of the second component, the mouse, are investigated in various situations: simple random walks in Z and Z^2, reflected simple random walk in N and also in a continuous time setting. For several of these processes, a time scaling with rapid growth gives an interesting asymptotic behavior related to limit results for occupation times and rare events of Markov processes.
Type de document :
Article dans une revue
Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2012, 22 (2)
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00383969
Contributeur : Philippe Robert <>
Soumis le : jeudi 14 mai 2009 - 07:31:04
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : jeudi 10 juin 2010 - 23:08:02

Fichiers

LR-Hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00383969, version 1
  • ARXIV : 0905.2259

Collections

Citation

Nelly Litvak, Philippe Robert. A Scaling Analysis of a Cat and Mouse Markov Chain. Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2012, 22 (2). 〈inria-00383969〉

Partager

Métriques

Consultations de la notice

260

Téléchargements de fichiers

166