Coupling and ergodic theorems for Markov chains with damping component
Authors:
D. Silvestrov, S. Silvestrov, B. Abola, P. S. Biganda, C. Engström, J. M. Mango and G. Kakuba
Journal:
Theor. Probability and Math. Statist. 101 (2020), 243-264
MSC (2020):
Primary 60J10, 60J22, 65C40; Secondary 90B15, 68M11
DOI:
https://doi.org/10.1090/tpms/1124
Published electronically:
January 5, 2021
Full-text PDF
Abstract |
References |
Similar Articles |
Additional Information
Abstract: Perturbed Markov chains are popular models for description of information networks. In such models, the transition matrix $\mathbf {P}_0$ of an information Markov chain is usually approximated by matrix $\mathbf {P}_{\varepsilon }=(1 - \varepsilon ) \mathbf {P}_0+\varepsilon \mathbf {D}$, where $\mathbf {D}$ is a so-called damping stochastic matrix with identical rows and all positive elements, while $\varepsilon \in [0, 1]$ is a damping (perturbation) parameter. Using procedure of artificial regeneration for the perturbed Markov chain $\eta _{\varepsilon , n}$, with the matrix of transition probabilities $\mathbf {P}_{\varepsilon }$, and coupling methods, we get ergodic theorems, in the form of asymptotic relations for \begin{equation*} p_{\varepsilon , ij}(n) =\mathsf {P}_i \{\eta _{\varepsilon , n}=j \} \end{equation*} as $n \to \infty$ and $\varepsilon \to 0$, and explicit upper bounds for the rates of convergence in such theorems. In particular, the most difficult case of the model with singular perturbations, where the phase space of the unperturbed Markov chain $\eta _{0, n}$ split in several closed classes of communicative states and possibly a class of transient states, is investigated.
References
- Benard Abola, Pitos Seleka Biganda, Christopher Engström, John Magero Mango, Godwin Kakuba, and Sergei Silvestrov, PageRank in evolving tree graphs, Stochastic processes and applications, Springer Proc. Math. Stat., vol. 271, Springer, Cham, 2018, pp. 375–390. MR 3903351, DOI https://doi.org/10.1007/978-3-030-02825-1_16
- Benard Abola, Pitos Seleka Biganda, Christopher Engström, John Magero Mango, Godwin Kakuba, and Sergei Silvestrov, PageRank in evolving tree graphs, Stochastic processes and applications, Springer Proc. Math. Stat., vol. 271, Springer, Cham, 2018, pp. 375–390. MR 3903351, DOI https://doi.org/10.1007/978-3-030-02825-1_16
- C. Engström and S. Silvestrov, PageRank for networks, graphs and Markov chains, Teor. Ĭmovīr. Mat. Stat. 96 (2017), 61–83 (English, with English, Russian and Ukrainian summaries); English transl., Theory Probab. Math. Statist. 96 (2018), 59–82. MR 3666872, DOI https://doi.org/10.1090/tpms/1034
- Fredrik K. Andersson and Sergei D. Silvestrov, The mathematics of internet search engines, Acta Appl. Math. 104 (2008), no. 2, 211–242. MR 2443279, DOI https://doi.org/10.1007/s10440-008-9254-y
- Konstantin E. Avrachenkov, Jerzy A. Filar, and Phil G. Howlett, Analytic perturbation theory and its applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2013. MR 3137641
- Konstantin Avrachenkov, Alexey Piunovskiy, and Yi Zhang, Hitting times in Markov chains with restart and their application to network centrality, Methodol. Comput. Appl. Probab. 20 (2018), no. 4, 1173–1188. MR 3873621, DOI https://doi.org/10.1007/s11009-017-9600-5
- S. Battiston, M. Puliga, R. Kaushik, P. Tasca, and G. Caldarelli, DebTrank: Too central to fail? financial networks, the FED and systemic risk, Scientific Reports 2 (2012), Article number 541.
- Pitos Seleka Biganda, Benard Abola, Christopher Engström, John Magero Mango, Godwin Kakuba, and Sergei Silvestrov, Traditional and lazy PageRanks for a line of nodes connected with complete graphs, Stochastic processes and applications, Springer Proc. Math. Stat., vol. 271, Springer, Cham, 2018, pp. 391–412. MR 3903352, DOI https://doi.org/10.1007/978-3-030-02825-1_17
- P. S. Biganda, B. Abola, C. Engström, and S. Silvestrov, PageRank, connecting a line of nodes with multiple complete graphs, Proceedings of the 17th Applied Stochastic Models and Data Analysis International Conference with the 6th Demographics Workshop. London, UK, 2017 (C. H. Skiadas, ed.), ISAST: International Society for the Advancement of Science and Technology, 2017, pp. 113–126.
- C. Engström and S. Silvestrov, PageRank for networks, graphs and Markov chains, Teor. Ĭmovīr. Mat. Stat. 96 (2017), 61–83 (English, with English, Russian and Ukrainian summaries); English transl., Theory Probab. Math. Statist. 96 (2018), 59–82. MR 3666872, DOI https://doi.org/10.1090/tpms/1034
- D. A. Bini, G. Latouche, and B. Meini, Numerical methods for structured Markov chains, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2005. Oxford Science Publications. MR 2132031
- S. Brin and L. Page, The anatomy of a large-scale hypertextual Web search engine, Comp. Networks, ISDN Syst. 30(1–7) (1998), 107–117.
- E. Englund, Nonlinearly Perturbed Renewal Equations with Applications, Doctoral dissertation, Umeå University, 2001.
- E. Englund and D. S. Silvestrov, Mixed large deviation and ergodic theorems for regenerative processes with discrete time, Proceedings of the Second Scandinavian–Ukrainian Conference in Mathematical Statistics, Vol. I, Umeå, 1997 (P. Jagers, G. Kulldorff, N. Portenko, D. Silvestrov, eds.), Theory Stoch. Process. 3(19) (1997), no. 1–2, 164–176.
- Christopher Engström and Mingqiang An, PageRank, a look at small changes in a line of nodes and the complete graph, Engineering mathematics. II, Springer Proc. Math. Stat., vol. 179, Springer, Cham, 2016, pp. 223–247. MR 3630581, DOI https://doi.org/10.1007/978-3-319-42105-6_11
- Christopher Engström and Sergei Silvestrov, Generalisation of the damping factor in PageRank for weighted networks, Modern problems in insurance mathematics, EAA Ser., Springer, Cham, 2014, pp. 313–333. MR 3330692
- Christopher Engström and Sergei Silvestrov, PageRank, connecting a line of nodes with a complete graph, Engineering mathematics. II, Springer Proc. Math. Stat., vol. 179, Springer, Cham, 2016, pp. 249–274. MR 3630582, DOI https://doi.org/10.1007/978-3-319-42105-6_12
- Christopher Engström and Sergei Silvestrov, PageRank, connecting a line of nodes with a complete graph, Engineering mathematics. II, Springer Proc. Math. Stat., vol. 179, Springer, Cham, 2016, pp. 249–274. MR 3630582, DOI https://doi.org/10.1007/978-3-319-42105-6_12
- C. Engström and S. Silvestrov, PageRank for networks, graphs and Markov chains, Teor. Ĭmovīr. Mat. Stat. 96 (2017), 61–83 (English, with English, Russian and Ukrainian summaries); English transl., Theory Probab. Math. Statist. 96 (2018), 59–82. MR 3666872, DOI https://doi.org/10.1090/tpms/1034
- William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
- Anna Gambin, Piotr Krzyżanowski, and Piotr Pokarowski, Aggregation algorithms for perturbed Markov chains with applications to networks modeling, SIAM J. Sci. Comput. 31 (2008), no. 1, 45–73. MR 2460770, DOI https://doi.org/10.1137/050624716
- David F. Gleich, PageRank beyond the web, SIAM Rev. 57 (2015), no. 3, 321–363. MR 3376760, DOI https://doi.org/10.1137/140976649
- David Griffeath, A maximal coupling for Markov chains, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 31 (1974/75), 95–106. MR 370771, DOI https://doi.org/10.1007/BF00539434
- Mats Gyllenberg and Dmitrii S. Silvestrov, Nonlinearly perturbed regenerative processes and pseudo-stationary phenomena for stochastic systems, Stochastic Process. Appl. 86 (2000), no. 1, 1–27. MR 1741194, DOI https://doi.org/10.1016/S0304-4149%2899%2900084-8
- Mats Gyllenberg and Dmitrii S. Silvestrov, Quasi-stationary phenomena in nonlinearly perturbed stochastic systems, De Gruyter Expositions in Mathematics, vol. 44, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. MR 2456816
- Esa Nummelin, General irreducible Markov chains and nonnegative operators, Cambridge Tracts in Mathematics, vol. 83, Cambridge University Press, Cambridge, 1984. MR 776608
- S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina, The EigenTrust algorithm for reputation management in P2P networks, Proceedings of the 12th International Conference on World Wide Web, ACM, 2003, pp. 640–651.
- Mihail Konstantinov, Da-Wei Gu, Volker Mehrmann, and Petko Petkov, Perturbation theory for matrix equations, Studies in Computational Mathematics, vol. 9, North-Holland Publishing Co., Amsterdam, 2003. MR 1991778
- Vladimir S. Koroliuk and Nikolaos Limnios, Stochastic systems in merging phase space, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. MR 2205562
- Vladimir S. Korolyuk and Vladimir V. Korolyuk, Stochastic models of systems, Mathematics and its Applications, vol. 469, Kluwer Academic Publishers, Dordrecht, 1999. MR 1753470
- Amy N. Langville and Carl D. Meyer, Google’s PageRank and beyond: the science of search engine rankings, Princeton University Press, Princeton, NJ, 2012. Paperback edition of the 2006 original. MR 3052718
- Torgny Lindvall, Lectures on the coupling method, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1992. A Wiley-Interscience Publication. MR 1180522
- A. Yu. Mitrophanov, Sensitivity and convergence of uniformly ergodic Markov chains, J. Appl. Probab. 42 (2005), no. 4, 1003–1014. MR 2203818, DOI https://doi.org/10.1239/jap/1134587812
- Ying Ni, Nonlinearly perturbed renewal equations: the non-polynomial case, Teor. Ĭmovīr. Mat. Stat. 84 (2011), 111–122 (English, with English, Russian and Ukrainian summaries); English transl., Theory Probab. Math. Statist. 84 (2012), 117–129. MR 2857422, DOI https://doi.org/10.1090/S0094-9000-2012-00865-X
- Y. Ni, D. Silvestrov, and A. Malyarenko, Exponential asymptotics for nonlinearly perturbed renewal equation with non-polynomial perturbations, J. Numer. Appl. Math. 1(96) (2008), 173–197.
- M. Petersson, Perturbed Discrete Time Stochastic Models, Doctoral dissertation, Stockholm University, 2016.
- J. W. Pitman, On coupling of Markov chains, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 35 (1976), no. 4, 315–322. MR 415775, DOI https://doi.org/10.1007/BF00532957
- D. S. Sīl′vestrov, The renewal theorem in the scheme of series. I, Teor. Verojatnost. i Mat. Statist. 18 (1978), 144–161, 183 (Russian, with English summary). MR 0488350
- D. S. Sīl′vestrov, The renewal theorem in the scheme of series. II, Teor. Veroyatnost. i Mat. Statist. 20 (1979), 97–116, 158 (Russian, with English summary). MR 529265
- D. S. Sil′vestrov, Method of a probability space in ergodic theorems for regenerative processes. I, Math. Operationsforsch. Statist. Ser. Optim. 14 (1983), no. 2, 285–299 (Russian, with English and German summaries). MR 701801, DOI https://doi.org/10.1080/02331938308842856
- D. S. Sil′vestrov, Method of a probability space in ergodic theorems for regenerative processes. II, III, Math. Operationsforsch. Statist. Ser. Optim. 15 (1984), no. 4, 601–612, 613–622 (Russian, with English and German summaries). MR 757138, DOI https://doi.org/10.1080/02331938408842977
- D. S. Sil′vestrov, Method of a probability space in ergodic theorems for regenerative processes. II, III, Math. Operationsforsch. Statist. Ser. Optim. 15 (1984), no. 4, 601–612, 613–622 (Russian, with English and German summaries). MR 757138, DOI https://doi.org/10.1080/02331938408842977
- Dmitrii S. Silvestrov, Coupling for Markov renewal processes and the rate of convergence in ergodic theorems for processes with semi-Markov switchings, Acta Appl. Math. 34 (1994), no. 1-2, 109–124. MR 1273849, DOI https://doi.org/10.1007/BF00994260
- Dmitrii Silvestrov, Individual ergodic theorems for perturbed alternating regenerative processes, Stochastic processes and applications, Springer Proc. Math. Stat., vol. 271, Springer, Cham, 2018, pp. 23–89. MR 3903338, DOI https://doi.org/10.1007/978-3-030-02825-1_3
- D. S. Silvestrov and M. Petersson, Exponential expansions for perturbed discrete time renewal equations, Applied Reliability Engineering and Risk Analysis (A. Karagrigoriou, A. Lisnianski, A. Kleyner, and I. Frenkel, eds.), Probabilistic Models and Statistical Inference, Wiley, New York, 2014, Chapter 23, pp. 349–362.
- Dmitrii Silvestrov, Mikael Petersson, and Ola Hössjer, Nonlinearly perturbed birth-death-type models, Stochastic processes and applications, Springer Proc. Math. Stat., vol. 271, Springer, Cham, 2018, pp. 189–244. MR 3903346, DOI https://doi.org/10.1007/978-3-030-02825-1_11
- D. S. Sil′vestrov and G. Pezhin′ska, Maximally coinciding random variables, Teor. Veroyatnost. i Mat. Statist. 32 (1985), 102–104, 135 (Russian). MR 882165
- Dmitrii Silvestrov and Sergei Silvestrov, Asymptotic expansions for stationary distributions of perturbed semi-Markov processes, Engineering mathematics. II, Springer Proc. Math. Stat., vol. 179, Springer, Cham, 2016, pp. 151–222. MR 3630580, DOI https://doi.org/10.1007/978-3-319-42105-6_10
- Dmitrii Silvestrov and Sergei Silvestrov, Nonlinearly perturbed semi-Markov processes, SpringerBriefs in Probability and Mathematical Statistics, Springer, Cham, 2017. MR 3700359
- Dmitrii Silvestrov and Sergei Silvestrov, Asymptotic expansions for stationary distributions of nonlinearly perturbed semi-Markov processes. 1, Methodol. Comput. Appl. Probab. 21 (2019), no. 3, 945–964. MR 4001861, DOI https://doi.org/10.1007/s11009-017-9605-0
- Dmitrii Silvestrov and Sergei Silvestrov, Asymptotic expansions for stationary distributions of nonlinearly perturbed semi-Markov processes. 1, Methodol. Comput. Appl. Probab. 21 (2019), no. 3, 945–964. MR 4001861, DOI https://doi.org/10.1007/s11009-017-9605-0
- D. S. Silvestrov and S. D. Silvestrov, Asymptotic expansions for power-exponential moments of hitting times for nonlinearly perturbed semi-Markov processes, Teor. Ĭmovīr. Mat. Stat. 97 (2017), 171–187 (English, with English, Russian and Ukrainian summaries); English transl., Theory Probab. Math. Statist. 97 (2018), 183–200. MR 3746007, DOI https://doi.org/10.1090/tpms/1056
- William J. Stewart, Introduction to the numerical solution of Markov chains, Princeton University Press, Princeton, NJ, 1994. MR 1312831
- G. W. Stewart, Matrix algorithms. Vol. I, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998. Basic decompositions. MR 1653546
- G. W. Stewart, Matrix algorithms. Vol. II, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. Eigensystems. MR 1853468
- Y. Sun and J. Han, Mining heterogeneous information networks: a structural analysis approach, ACM SIGKDD Explor. Newslet. 14(2) (2013), 20–28.
- G. George Yin and Qing Zhang, Discrete-time Markov chains, Applications of Mathematics (New York), vol. 55, Springer-Verlag, New York, 2005. Two-time-scale methods and applications; Stochastic Modelling and Applied Probability. MR 2092994
- G. George Yin and Qing Zhang, Continuous-time Markov chains and applications, 2nd ed., Stochastic Modelling and Applied Probability, vol. 37, Springer, New York, 2013. A two-time-scale approach. MR 2985157
References
- B. Abola, P. S. Biganda, C. Engström, J. M. Mango, G. Kakuba, and S. Silvestrov, PageRank in evolving tree graphs, Stochastic Processes and Applications (S. Silvestrov, M. Ranc̆ić, and A. Malyarenko, eds.), Springer Proceedings in Mathematics & Statistics, vol. 271, Springer, Cham, 2018, Chapter 16, pp. 375–390. MR 3903351
- B. Abola, P. S. Biganda, C. Engström, J. M. Mango, G. Kakuba, and S. Silvestrov, Updating of PageRank in evolving tree graphs, Proceedings of the 5th Stochastic Modeling Techniques and Data Analysis International Conference with Demographics Workshop, Chania, Crete, Greece, 2018 (C. H. Skiadas, ed.), ISAST: International Society for the Advancement of Science and Technology, 2018, pp. 15–26. MR 3903351
- B. Abola, P. S. Biganda, S. Silvestrov, D. Silvestrov, C. Engström, J. M. Mango, and G. Kakuba, Perturbed Markov chains and information networks, arXiv:1901.11483, 2019. MR 3666872
- F. K. Andersson and S. D. Silvestrov, The mathematics of Internet search engines, Acta Appl. Math. 104 (2008), no. 2, 211–242. MR 2443279
- K. E. Avrachenkov, J. A. Filar, and P. G. Howlett, Analytic Perturbation Theory and Its Applications, SIAM, Philadelphia, 2013. MR 3137641
- K. Avrachenkov, A. Piunovskiy, and Yi Zhang, Hitting times in Markov chains with restart and their application to network centrality, Methodol. Comput. Appl. Probab. 20 (2018), no. 4, 1173–1188. MR 3873621
- S. Battiston, M. Puliga, R. Kaushik, P. Tasca, and G. Caldarelli, DebTrank: Too central to fail? financial networks, the FED and systemic risk, Scientific Reports 2 (2012), Article number 541.
- P. S. Biganda, B. Abola, C. Engström, J. M. Mango, G. Kakuba, and S. Silvestrov, Traditional and lazy PageRanks for a line of nodes connected with complete graphs, Stochastic Processes and Applications (S. Silvestrov, M. Ranc̆ić, and A. Malyarenko, eds.), Springer Proceedings in Mathematics & Statistics, vol. 271, Springer, Cham, 2018, Chapter 17, pp. 391–412. MR 3903352
- P. S. Biganda, B. Abola, C. Engström, and S. Silvestrov, PageRank, connecting a line of nodes with multiple complete graphs, Proceedings of the 17th Applied Stochastic Models and Data Analysis International Conference with the 6th Demographics Workshop. London, UK, 2017 (C. H. Skiadas, ed.), ISAST: International Society for the Advancement of Science and Technology, 2017, pp. 113–126.
- P. S. Biganda, B. Abola, C. Engström, J. M. Mango, G. Kakuba, and S. Silvestrov, Exploring the relationship between ordinary PageRank, lazy PageRank and random walk with back step PageRank for different graph structures, Proceedings of the 5th Stochastic Modeling Techniques and Data Analysis International Conference with Demographics Workshop, Chania, Crete, Greece, 2018 (C. H. Skiadas, ed.), ISAST: International Society for the Advancement of Science and Technology, 2018, pp. 71–85. MR 3666872
- D. A. Bini, G. Latouche, and B. Meini, Numerical Methods for Structured Markov Chains, Numerical Mathematics and Scientific Computation, Oxford Science Publications, Oxford University Press, New York, 2005. MR 2132031
- S. Brin and L. Page, The anatomy of a large-scale hypertextual Web search engine, Comp. Networks, ISDN Syst. 30(1–7) (1998), 107–117.
- E. Englund, Nonlinearly Perturbed Renewal Equations with Applications, Doctoral dissertation, Umeå University, 2001.
- E. Englund and D. S. Silvestrov, Mixed large deviation and ergodic theorems for regenerative processes with discrete time, Proceedings of the Second Scandinavian–Ukrainian Conference in Mathematical Statistics, Vol. I, Umeå, 1997 (P. Jagers, G. Kulldorff, N. Portenko, D. Silvestrov, eds.), Theory Stoch. Process. 3(19) (1997), no. 1–2, 164–176.
- C. Engström, PageRank in Evolving Networks and Applications of Graphs in Natural Language Processing and Biology, Doctoral dissertation, vol. 217, Mälardalen University, Västerås, 2016. MR 3630581
- C. Engström and S. Silvestrov, Generalisation of the damping factor in PageRank for weighted networks, Modern Problems in Insurance Mathematics (D. Silvestrov and A. Martin-Löf, eds.), EAA series, Springer, Cham, 2014, Chapter 19, pp. 313–334. MR 3330692
- C. Engström and S. Silvestrov, PageRank, a look at small changes in a line of nodes and the complete graph, Engineering Mathematics II. Algebraic, Stochastic and Analysis Structures for Networks, Data Classification and Optimization (S. Silvestrov and M. Ranc̆ić, eds.), Springer Proceedings in Mathematics & Statistics, vol. 179, Springer, Cham, 2016, Chapter 11, pp. 223–248. MR 3630582
- C. Engström and S. Silvestrov, PageRank, connecting a line of nodes with a complete graph, Engineering Mathematics II. Algebraic, Stochastic and Analysis Structures for Networks, Data Classification and Optimization (S. Silvestrov and M. Ranc̆ić, eds.), Springer Proceedings in Mathematics & Statistics, vol. 179, Springer, Cham, 2016, Chapter 12, pp. 249–274. MR 3630582
- C. Engström and S. Silvestrov, PageRank for networks, graphs, and Markov chains, Teor. Ĭmovirn. Mat. Stat. 96 (2017), 61–83; English transl. in Theor. Probab. Math. Statist. 96, 59–82. MR 3666872
- W. Feller, An Introduction to Probability Theory and Its Applications, Vol. I, Third edition, Wiley, New York, 1968. MR 0228020
- A. Gambini, P. Krzyanowski, and P. Pokarowski, Aggregation algorithms for perturbed Markov chains with applications to networks modeling, SIAM J. Sci. Comput. 31, (2008), no. 1, 45–73. MR 2460770
- D. F. Gleich, PageRank beyond the Web, SIAM Review 57(3) (2015), 321–363. MR 3376760
- D. Griffeath, A maximal coupling for Markov chains, Z. Wahrsch. verw. Gebiete 31 (1975), 95–106. MR 370771
- M. Gyllenberg and D. S. Silvestrov, Nonlinearly perturbed regenerative processes and pseudo-stationary phenomena for stochastic systems, Stoch. Process. Appl. 86 (2000), 1–27. MR 1741194
- M. Gyllenberg and D. S. Silvestrov, Quasi-Stationary Phenomena in Nonlinearly Perturbed Stochastic Systems, De Gruyter Expositions in Mathematics, vol. 44, Walter de Gruyter, Berlin, 2008. MR 2456816
- V. V. Kalashnikov, Coupling method, development and applications. Appendix to the Russian edition of the book: E. Nummelin, General irreducible Markov Chains and Non-negative Operators, Cambridge Tracts in Mathematics, vol. 83, Cambridge University Press, 1984; Russian edition, “Mir”, Moscow, 1989, pp. 176–190. MR 776608
- S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina, The EigenTrust algorithm for reputation management in P2P networks, Proceedings of the 12th International Conference on World Wide Web, ACM, 2003, pp. 640–651.
- M. Konstantinov, D. W. Gu, V. Mehrmann, and P. Petkov, Perturbation Theory for Matrix Equations, Studies in Computational Mathematics, vol. 9, North-Holland, Amsterdam, 2003. MR 1991778
- V. S. Koroliuk and N. Limnios, Stochastic Systems in Merging Phase Space, World Scientific, Singapore, 2005. MR 2205562
- V. S. Koroliuk and V. V. Koroliuk, Stochastic Models of Systems, Mathematics and Its Applications, vol. 469, Kluwer, Dordrecht, 1999. MR 1753470
- A. N. Langville and C. D. Meyer, Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, 2011. MR 3052718
- T. Lindvall, Lectures on the Coupling Method, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, A revised reprint of the 1992 original, Wiley, New York, 2002. MR 1180522
- A. Yu. Mitrophanov, Sensitivity and convergence of uniformly ergodic Markov chains, J. Appl. Probab. 42 (2005), 1003–1014. MR 2203818
- Y. Ni, Nonlinearly Perturbed Renewal Equations: Asymptotic Results and Applications, Doctoral dissertation, vol. 106, Mälardalen University, Västerås, 2011. MR 2857422
- Y. Ni, D. Silvestrov, and A. Malyarenko, Exponential asymptotics for nonlinearly perturbed renewal equation with non-polynomial perturbations, J. Numer. Appl. Math. 1(96) (2008), 173–197.
- M. Petersson, Perturbed Discrete Time Stochastic Models, Doctoral dissertation, Stockholm University, 2016.
- J. W. Pitman, On coupling of Markov chains, Z. Wahrsch. verw. Gebiete 35 (1979), 315–322. MR 415775
- D. S. Silvestrov, The renewal theorem in a series scheme. 1, Teor. Veroyatn. Mat. Stat. 18 (1978), 144–161; English transl. in Theory Probab. Math. Statist. 18, 155–172. MR 0488350
- D. S. Silvestrov, The renewal theorem in a series scheme 2, Teor. Veroyatn. Mat. Stat. 20 (1979), 97–116; English transl. in Theory Probab. Math. Statist. 20, 113–130. MR 529265
- D. S. Silvestrov, Method of a single probability space in ergodic theorems for regenerative processes 1, Math. Operat. Statist., Ser. Optim. 14 (1983), 285–299. MR 701801
- D. S. Silvestrov, Method of a single probability space in ergodic theorems for regenerative processes 2, Math. Operat. Statist., Ser. Optim. 15 (1984), 601–612. MR 757138
- D. S. Silvestrov, Method of a single probability space in ergodic theorems for regenerative processes 3, Math. Operat. Statist., Ser. Optim. 15 (1984), 613–622. MR 757138
- D. Silvestrov, Coupling for Markov renewal processes and the rate of convergence in ergodic theorems for processes with semi-Markov switchings, Acta Applic. Math. 34 (1994) 109–124. MR 1273849
- D. Silvestrov, Individual ergodic theorems for perturbed alternating regenerative processes, Stochastic Processes and Applications (S. Silvestrov, M. Ranc̆ić, and A. Malyarenko, eds.), Springer Proceedings in Mathematics & Statistics, vol. 271, Springer, Cham, 2018, Chapter 3, pp. 23–90. MR 3903338
- D. S. Silvestrov and M. Petersson, Exponential expansions for perturbed discrete time renewal equations, Applied Reliability Engineering and Risk Analysis (A. Karagrigoriou, A. Lisnianski, A. Kleyner, and I. Frenkel, eds.), Probabilistic Models and Statistical Inference, Wiley, New York, 2014, Chapter 23, pp. 349–362.
- D. S. Silvestrov, M. Petersson, and O. Hössjer, Nonlinearly perturbed birth-death-type models, Stochastic Processes and Applications (S. Silvestrov, M. Ranc̆ić, and A. Malyarenko, eds.), Springer Proceedings in Mathematics & Statistics, vol. 271, Springer, Cham, 2018, Chapter 11, pp. 189–244. MR 3903346
- D. S. Silvestrov and G. Pezinska, On maximally coinciding random variables, Theor. Veroyatn. Mat. Stat. 32 (1985), 102–105; English transl. in Theory Probab. Math. Statist. 32, 113–115. MR 882165
- D. Silvestrov and S. Silvestrov, Asymptotic expansions for stationary distributions of perturbed semi-Markov processes, Engineering Mathematics II. Algebraic, Stochastic and Analysis Structures for Networks, Data Classification and Optimization (S. Silvestrov and M. Ranc̆ić, eds.), Springer Proceedings in Mathematics & Statistics, vol. 179, Springer, Cham, 2016, Chapter 10, pp. 151–222. MR 3630580
- D. Silvestrov and S. Silvestrov, Nonlinearly Perturbed Semi-Markov Processes, Springer Briefs in Probability and Mathematical Statistics, Springer, Cham, 2017. MR 3700359
- D. Silvestrov and S. Silvestrov, Asymptotic expansions for stationary distributions of nonlinearly perturbed semi-Markov processes. 1, Methodol. Comput. Appl. Probab., doi.org/10.1007/s11009-017-9605-0, 2017. MR 4001861
- D. Silvestrov and S. Silvestrov, Asymptotic expansions for stationary distributions of nonlinearly perturbed semi-Markov processes. 2, Methodol. Comput. Appl. Probab., doi.org/10.1007/s11009-017-9607-yh, 2017. MR 4001861
- D. Silvestrov and S. Silvestrov, Asymptotic expansions for power-exponential moments of hitting times for nonlinearly perturbed semi-Markov processes, Teor. Ĭmovirn. Mat. Stat. 97 (2017), 171–187; English transl. in Theory Probab. Math. Statist. 97, 183–200. MR 3746007
- G. W. Stewart, Introduction to the Numerical Solution of Markov chains, Princeton University Press, Princeton, NJ, 1994. MR 1312831
- G. W. Stewart, Matrix Algorithms, Vol. I. Basic Decompositions. SIAM, Philadelphia, PA, 1998. MR 1653546
- G. W. Stewart, Matrix Algorithms, Vol. II. Eigensystems. SIAM, Philadelphia, PA, 2001. MR 1853468
- Y. Sun and J. Han, Mining heterogeneous information networks: a structural analysis approach, ACM SIGKDD Explor. Newslet. 14(2) (2013), 20–28.
- G. G. Yi and Q. Zhang, Discrete-Time Markov Chains. Two-Time-Scale Methods and Applications, Stochastic Modelling and Applied Probability, vol. 55, Springer, New York, 2005. MR 2092994
- G. G. Yi and Q. Zhang, Continuous-Time Markov Chains and Applications. A Two-Time-Scale Approach, Second edition, Stochastic Modelling and Applied Probability, vol. 37, Springer, New York, 2013. MR 2985157
Similar Articles
Retrieve articles in Theory of Probability and Mathematical Statistics
with MSC (2020):
60J10,
60J22,
65C40,
90B15,
68M11
Retrieve articles in all journals
with MSC (2020):
60J10,
60J22,
65C40,
90B15,
68M11
Additional Information
D. Silvestrov
Affiliation:
Department of Mathematics, Stockholm University, 106 81 Stockholm, Sweden
Email:
silvestrov@math.su.se
S. Silvestrov
Affiliation:
Division of Applied Mathematics, School of Education, Culture and Communication, Mälardalen University, Box 883, 721 23, Västerås, Sweden
Email:
sergei.silvestrov@mdh.se
B. Abola
Affiliation:
Division of Applied Mathematics, School of Education, Culture and Communication, Mälardalen University, Box 883, 721 23, Västerås, Sweden
Email:
benard.abola@mdh.se
P. S. Biganda
Affiliation:
Department of Mathematics, College of Natural and Applied Sciences, University of Dar es Salaam, Box 35062, Dar es Salaam, Tanzania
Address at time of publication:
Division of Applied Mathematics, School of Education, Culture and Communication, Mälardalen University, Box 883, 721 23, Västerås, Sweden
Email:
pitos.biganda@mdh.se
C. Engström
Affiliation:
Division of Applied Mathematics, School of Education, Culture and Communication, Mälardalen University, Box 883, 721 23, Västerås, Sweden
Email:
christopher.engstrom@mdh.se
J. M. Mango
Affiliation:
Department of Mathematics, School of Physical Sciences, Makerere University, Box 7062, Kampala, Uganda
Email:
mango@cns.mak.ac.ug
G. Kakuba
Affiliation:
Department of Mathematics, School of Physical Sciences, Makerere University, Box 7062, Kampala, Uganda
Email:
godwin.a.kakuba@gmail.com
Keywords:
Markov chain,
damping component,
information network,
regular perturbation,
singular perturbation,
coupling,
ergodic theorem,
rate of convergence,
triangular array mode
Received by editor(s):
September 13, 2019
Published electronically:
January 5, 2021
Article copyright:
© Copyright 2021
American Mathematical Society