Computing Absorbing Times via Fluid Approximations

Nicolas Gast 1 Bruno Gaujal 1
1 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper, we compute the absorbing time Tn of a n-dimensional discrete time Markov chain made of n components, each with an absorbing state and evolving in mutual exclusion. We show that the random absorbing time Tn is well approximated by a deterministic time tn that is the first time when a fluid approximation of the chain approaches the absorbing state at a distance 1/n. We provide an asymptotic expansion of tn that uses the spectral decomposition of the kernel of the chain as well as the asymptotic distribution of Tn, relying on extreme values theory. We show the applicability of this approach with three different problems: the coupon collector, the erasure channel lifetime and the coupling times of random walks in high dimensional spaces.
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01553138
Contributeur : Nicolas Gast <>
Soumis le : mardi 4 juillet 2017 - 10:09:46
Dernière modification le : jeudi 6 juillet 2017 - 01:04:42

Fichier

gastGaujal_absorbingTimeFluid_...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01553138, version 1

Citation

Nicolas Gast, Bruno Gaujal. Computing Absorbing Times via Fluid Approximations. Advances in Applied Probability, Applied Probability Trust, 2017. 〈hal-01553138〉

Partager

Métriques

Consultations de
la notice

147

Téléchargements du document

57