2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
1986
1985
1984
1983
1982
1981
1980
1979
1978
1977
1976
1975
1974
1973
1972
1971
1970


Archive

About   Editorial Board   Contacts   Template   Publication Ethics   Peer Review Process

Theory of Probability and Mathematical Statistics
(Teoriya Imovirnostei ta Matematychna Statystyka)



Coupling and Ergodic Theorems for Markov Chains with Damping Component

D. Silvestrov, S. Silvestrov, B. Abola, P. S. Biganda, C. Engstrom, J. M. Mango, G. Kakuba

Download PDF

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 $p_{\varepsilon, ij}(n) \hm= \PP_i \{\eta_{\varepsilon, n} = j \}$, 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.

Keywords: Markov chain, Damping component, Information network, Regular perturbation, Singular perturbation, Coupling, Ergodic theorem, Rate of convergence, Triangular array mode.

Bibliography:
1. B. Abola, P. S. Biganda, C. Engstrom, J. M. Mango, G. Kakuba, S. Silvestrov, PageRank in evolving tree graphs, Stochastic Processes and Applications (S. Silvestrov, M. Ran˘cic, A. Malyarenko, eds.), Springer Proceedings in Mathematics & Statistics, 271, Springer, Cham, 2018, Chapter 16, 375–390.
2. B. Abola, P. S. Biganda, C. Engstrom, J. M. Mango, G. Kakuba, 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, 15–26.
3. B. Abola, P. S. Biganda, S. Silvestrov, D. Silvestrov, C. Engstrom, J. M. Mango, G. Kakuba, Perturbed Markov chains and information networks, arXiv:1901.11483, 59 p. (2019).
4. F. K. Andersson, S. D. Silvestrov, The mathematics of internet search engines, Acta Applic. Math. 104 (2008), no. 2, 211–242.
5. K. E. Avrachenkov, J. A. Filar, P. G. Howlett, Analytic Perturbation Theory and Its Applications, SIAM, Philadelphia, 2013.
6. K. Avrachenkov, A. Piunovskiy, 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.
7. S. Battiston, M. Puliga, R. Kaushik, P. Tasca, G. Caldarelli, Debtrank: Too central to fail? financial networks, the fed and systemic risk, Scientific Reports, 2, Art. num. 541 (2012).
8. P. S. Biganda, B. Abola, C. Engstrom, J. M. Mango, G. Kakuba, S. Silvestrov, Traditional and lazy PageRanks for a line of nodes connected with complete graphs, Stochastic Processes and Applications (S. Silvestrov, M. Rancic, A. Malyarenko, eds.), Springer Proceedings in Mathematics & Statistics, 271, Springer, Cham, 2018, Chapter 17, 391–412.
9. P. S. Biganda, B. Abola, C. Engstrom, 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, 113–126.
10. P. S. Biganda, B. Abola, C. Engstrom, J. M. Mango, G. Kakuba, 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, 71–85.
11. D. A. Bini, G. Latouche, B. Meini, Numerical Methods for Structured Markov Chains, Numerical Mathematics and Scientific Computation, Oxford Science Publications, Oxford University Press, New York, 2005.
12. S. Brin, L. Page, The anatomy of a large-scale hypertextual web search engine, Comp. Networks, ISDN Syst. 30(1-7), (1998), 107–117.
13. E. Englund, Nonlinearly Perturbed Renewal Equations with Applications, Doctoral dissertation, Umea University, 2001.
14. E. Englund, 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, Umea, 1997 (P. Jagers, G. Kulldorff, N. Portenko, D. Silvestrov, eds.), Theory Stoch. Process. 3(19) (1997), no. 1-2, 164–176.
15. C. Engstrom, PageRank in Evolving Networks and Applications of Graphs in Natural Language Processing and Biology, Doctoral dissertation 217, Malardalen University, Vasteras, 2016.
16. C. Engstrom, S. Silvestrov, Generalisation of the damping factor in PageRank for weighted networks, Modern Problems in Insurance Mathematics (D. Silvestrov, A. Martin-Lof, eds.), EAA series, Springer, Cham, 2014, Chapter 19, 313–334.
17. C. Engstrom, 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, M. Ranci´c, eds.), Springer Proceedings in Mathematics & Statistics, 179, Springer, Cham, 2016, Chapter 11. 223–248.
18. C. Engstrom, 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, M. Rancic, eds.), Springer Proceedings in Mathematics & Statistics ,179, Springer, Cham, 2016, Chapter 12, 249–274.
19. C. Engstrom, S. Silvestrov, PageRank for networks, graphs, and Markov chains, Teor. Imovirn. Mat. Stat., 96 (2017), 61–83 (Also, in Theor. Probab. Math. Statist., 96, 59–82).
20. W. Feller, An Introduction to Probability Theory and Its Applications, Vol. I, Third edition, Wiley, New York, 1968.
21. A. Gambini, P. Krzyanowski, P. Pokarowski, Aggregation algorithms for perturbed Markov chains with applications to networks modeling, SIAM J. Sci. Comput. 31, (2008), no. 1, 45–73.
22. D. F. Gleich, PageRank beyond the Web, SIAM Review, 57(3) (2015), 321–363.
23. D. Griffeath, A maximal coupling for Markov chains, Z. Wahrsch. verw. Gebiete, 31 (1975), 95–106.
24. M. Gyllenberg, D. S. Silvestrov. Nonlinearly perturbed regenerative processes and pseudostationary phenomena for stochastic systems, Stoch. Process. Appl., 86 (2000), 1–27.
25. M. Gyllenberg, D. S. Silvestrov, Quasi-Stationary Phenomena in Nonlinearly Perturbed Stochastic Systems, De Gruyter Expositions in Mathematics, 44, Walter de Gruyter, Berlin, 2008.
26. V. V. Kalashnikov, Coupling method, development and applications. Appendix to the Russian edition of the book: E. Nummelin, General lrreducible Markov Chains and Non-negative Operators, Cambridge Tracts in Mathematics, 83, Cambridge University Press, 1984 (Russian edition, MIR, Moscow, 1989, 176–190).
27. S. D. Kamvar, M. T. Schlosser, H. Garcia-Molina, The eigentrust algorithm for reputation management in p2p networks, Proceedings of the 12th International Conference on World Wide Web, ACM, 2003, 640–651.
28. M. Konstantinov, D. W. Gu, V. Mehrmann, P. Petkov, Perturbation Theory for Matrix Equations, Studies in Computational Mathematics, 9, North-Holland, Amsterdam, 2003.
29. V. S. Koroliuk, N. Limnios, Stochastic Systems in Merging Phase Space, World Scientific, Singapore, 2005.
30. V. S. Koroliuk, V.V. Koroliuk, Stochastic Models of Systems, Mathematics and Its Applications, 469, Kluwer, Dordrecht, 1999.
31. A. N. Langville, C. D. Meyer, Google’s PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, Princeton, 2011.
32. T. Lindvall, Lectures on the Coupling Method, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, Wiley, New York, 2002 (A revised reprint of the 1992 original).
33. A. Yu. Mitrophanov, Sensitivity and convergence of uniformly ergodic Markov chains, J. Appl. Prob., 42 (2005), 1003–1014.
34. Y. Ni, Nonlinearly Perturbed Renewal Equations: Asymptotic Results and Applications, Doctoral dissertation, 106, M¨alardalen University, Vasteras, 2011.
35. Y. Ni, D. Silvestrov, A. Malyarenko, Exponential asymptotics for nonlinearly perturbed renewal equation with non-polynomial perturbations, J. Numer. Appl. Math., 1(96) (2008), 173–197.
36. M. Petersson, Perturbed Discrete Time Stochastic Models, Doctoral dissertation, Stockholm University, 2016.
37. J. W. Pitman, On coupling of Markov chains, Z. Wahrsch. verw. Gebiete, 35 (1979), 315–322.
38. D. S. Silvestrov, The renewal theorem in a series scheme. 1, Teor. Veroyatn. Mat. Stat., 18 (1978), 144–161 (English translation in Theory Probab. Math. Statist., 18, 155–172).
39. D. S. Silvestrov, The renewal theorem in a series scheme 2, Teor. Veroyatn. Mat. Stat., 20 (1979) 97–116 (English translation in Theory Probab. Math. Statist., 20, 113–130).
40. 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.
41. 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.
42. 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.
43. 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.
44. D. Silvestrov, Individual ergodic theorems for perturbed alternating regenerative processes, Stochastic Processes and Applications (S. Silvestrov, M. Rancic, A. Malyarenko, eds.), Springer Proceedings in Mathematics & Statistics, 271, Springer, Cham, 2018, Chapter 3, 23–90.
45. D. S. Silvestrov, M. Petersson, Exponential expansions for perturbed discrete time renewal equations, Applied Reliability Engineering and Risk Analysis (A. Karagrigoriou, A. Lisnianski, A. Kleyner, I. Frenkel, eds.), Probabilistic Models and Statistical Inference, Wiley, New York, 2014, Chapter 23, 349–362.
46. D. S. Silvestrov, M. Petersson, O. H¨ossjer, Nonlinearly perturbed birth-death-type models, Stochastic Processes and Applications (S. Silvestrov, M. Rancic, A. Malyarenko, eds.), Springer Proceedings in Mathematics & Statistics, 271, Springer, Cham, 2018, Chapter 11, 189–244.
47. D. S. Silvestrov, G. Pezinska, On maximally coinciding random variables, Theor. Veroyatn. Mat. Stat, 32, (1985), 102–105 (English translation in Theory Probab. Math. Statist., 32, 113–115).
48. D. Silvestrov, 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, M. Ran˘ci´c, eds.), Springer Proceedings in Mathematics & Statistics, 179, Springer, Cham, 2016, Chapter 10, 151–222.
49. D. Silvestrov, S. Silvestrov, Nonlinearly Perturbed Semi-Markov Processes, Springer Briefs in Probability and Mathematical Statistics, Springer, Cham, 2017.
50. D. Silvestrov, 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, 20 p. (2017).
51. D. Silvestrov, 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, 20 p. (2017).
52. D. Silvestrov, S. Silvestrov, Asymptotic expansions for power-exponential moments of hitting times for nonlinearly perturbed semi-Markov processes, Teor. ˘Imovirn. Mat. Stat., 97 (2017), 171–187 (Also, in Theory Probab. Math. Statist., 97, 183–200).
53. G. W. Stewart, Introduction to the Numerical Solution of Markov chains, Princeton University Press, Princeton, NJ, 1994.
54. G. W. Stewart, Matrix Algorithms, Vol. I. Basic Decompositions. SIAM, Philadelphia, PA, 1998.
55. G. W. Stewart, Matrix Algorithms, Vol. II. Eigensystems. SIAM, Philadelphia, PA, 2001.
56. Y. Sun, J. Han, Mining heterogeneous information networks: a structural analysis approach, ACM SIGKDD Explor. Newslet., 14(2) (2013), 20–28.
57. G. G. Yi, Q. Zhang, Discrete-Time Markov Chains. Two-Time-Scale Methods and Applications, Stochastic Modelling and Applied Probability, 55, Springer, New York, 2005.
58. G. G. Yi, Q. Zhang, Continuous-Time Markov Chains and Applications. A Two-Time-Scale Approach, Second edition, Stochastic Modelling and Applied Probability, 37, Springer, New York, 2013 (An extended variant of the first (1998) edition).