Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T17:01:19.183Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing absorbing times via fluid approximations

Part of: Ergodic theory Markov processes Extremal combinatorics

Published online by Cambridge University Press:  08 September 2017

Nicolas Gast  and
Bruno Gaujal
Nicolas Gast*
Affiliation:
Université Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
Bruno Gaujal*
Affiliation:
Université Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
*
* Postal address: Institute of Engineering, Université Grenoble Alpes, Inria, Bâtiment IMAG, 700 avenue Centrale, 38400 St Martin d'Heres, France.
* Postal address: Institute of Engineering, Université Grenoble Alpes, Inria, Bâtiment IMAG, 700 avenue Centrale, 38400 St Martin d'Heres, France.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we compute the absorbing time T n of an n-dimensional discrete-time Markov chain comprising n components, each with an absorbing state and evolving in mutual exclusion. We show that the random absorbing time T n is well approximated by a deterministic time t n 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 t n that uses the spectral decomposition of the kernel of the chain as well as the asymptotic distribution of T n , 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.

Keywords

Markov chainfluid approximationextreme valuecoupon collectorcoupling time

MSC classification

Primary: 05D40: Probabilistic methods
Secondary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 37A25: Ergodicity, mixing, rates of mixing

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 3 , September 2017 , pp. 768 - 790
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Anceaume, E., Busnel, Y. and Sericola, B. (2015). New results on a generalized coupon collector problem using Markov chains. J. Appl. Prob. 52, 405–418. CrossRefGoogle Scholar
[2] Benaïm, M. and Le Boudec, J.-Y. (2008). A class of mean field interaction models for computer and communication systems. Performance Evaluation 65, 823–838. Google Scholar
[3] Berenbrink, P. and Sauerwald, T. (2009). The weighted coupon collector's problem and applications. In Computing and Combinatorics, Springer, Berlin, pp. 449–458. CrossRefGoogle Scholar
[4] Brayton, R. K. (1963). On the asymptotic behavior of the number of trials necessary to complete a set with random selection. J. Math. Anal. Appl. 7, 31–61. Google Scholar
[5] Chaintreau, A., Le Boudec, J.-Y. and Ristanovic, N. (2009). The age of gossip: spatial mean field regime. ACM SIGMETRICS Performance Eval. Rev. 37, 109–120. Google Scholar
[6] Chazottes, J.-R., Collet, P. and Méléard, S. (2016). Sharp asymptotics for the quasi-stationary distribution of birth-and-death processes. Prob. Theory Relat. Fields 164, 285–332. Google Scholar
[7] Doumas, A. V. and Papanicolaou, V. G. (2012). The coupon collector's problem revisited: asymptotics of the variance. Adv. Appl. Prob. 44, 166–195. Google Scholar
[8] Doumas, A. V. and Papanicolaou, V. G. (2016). The coupon collector's problem revisited: generalizing the double dixie cup problem of Newman and Shepp. ESAAIM Prob. Statist. 20, 367–399. Google Scholar
[9] Erdős, P. and Rényi, A. (1961). On a classical problem of probability theory. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6, 215–220. Google Scholar
[10] Flajolet, P., Gardy, D. and Thimonier, L. (1992). Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Appl. Math. 39, 207–229. Google Scholar
[11] Ganesh, A. et al. (2012). Load balancing via random local search in closed and open systems. Queueing Systems 71, 321–345. Google Scholar
[12] Gast, N. and Bruno, G. (2010). A mean field model of work stealing in large-scale systems. ACM SIGMETRICS Performance Eval. Rev. 38, 13–24. Google Scholar
[13] Kang, W. and Ramanan, K. (2012). Asymptotic approximations for stationary distributions of many-server queues with abandonment. Ann. Appl. Prob. 22, 477–521. Google Scholar
[14] Kulkarni, D., Schmidt, D. and Tsui, S.-K. (1999). Eigenvalues of tridiagonal pseudo-Toeplitz matrices. Linear Algebra Appl. 297, 63–80. Google Scholar
[15] Kurtz, T. G. (1978). Strong approximation theorems for density dependent Markov chains. Stoch. Process. Appl. 6, 223–240. Google Scholar
[16] Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. Society for Industrial and Applied Mathematics, Philadelphia, PA. Google Scholar
[17] Le Boudec, J.-Y. (2013). The stationary behaviour of fluid limits of reversible processes is concentrated on stationary points. Networks Heterogeneous Media 8, 529–540. CrossRefGoogle Scholar
[18] Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times. American Mathematical Society, Providence, RI. Google Scholar
[19] May, R. (2008). Coupon collecting with quotas. Electron. J. Combinatorics 15, 31. Google Scholar
[20] Neal, P. (2008). The generalised coupon collector problem. J. Appl. Prob. 45, 621–629. Google Scholar
[21] Newman, D. J. and Shepp, L. (1960). The double dixie cup problem. Amer. Math. Monthly 67, 58–61. Google Scholar
[22] Propp, J. G. and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9, 223–252. Google Scholar
[23] Shank, N. and Yang, H. (2013). Coupon collector problem for nonuniform coupons and random quotas. Electron. J. Combinatorics 20, 33. Google Scholar