On special properties of some quasi-metrics

E. I. Deza ; B. Mhanna

Čebyševskij sbornik, Tome 21 (2020) no. 1, pp. 145-164.

Résumé

In this paper we consider some questions of the theory and practice of mean first passage time quasi-metric, a generalized metric structure closely related to ergodic homogeneous Markov chains. The introduction considers the history of the problem and provides an overview of the main ideas and results presented in the article. The first section gives the basic concepts of the theory of Markov chains. In fact, a Markov chain is a mathematical model of some random process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. The second section collects the basic definitions needed to consider the role of graph models in the presentation and study of ergodic homogeneous Markov chains. The Markov chain can be depicted as an oriented weighted graph of transitions whose vertices correspond to the states of the chain and the arcs correspond to the transitions between them. The process will be ergodic if this weighted oriented graph is weakly connected, and the largest common divisor of the lengths of all its cycles is equal to $1$. On the other hand, any connected graph can be used as a basis for building a model of the simplest Markov chain: if a vertex $i$ has degree $k$, all incident edges are converted into arcs with the weights $\frac{1}{k}$. In the third section the definition of the mean first passage time for an ergodic homogeneous Markov chain is given. There are several ways to build the corresponding matrix. The algorithm of finding the mean first passage time is analyzed in detail by using converging trees of the oriented graph, related to the transition matrix of the ergodic homogeneous Markov chain. Related recurrent procedure is described. In the fourth section, a mean first passage time is analyzed as the quasi-metric $m$ of mean first passage time on the vertices $V =\{1, 2,..., n\}$ of the oriented graph corresponding to the transition matrix of a given ergodic homogeneous Markov chain: $m(i, j)$ is the expected number of steps (arcs) for random wandering on the oriented graph $\Gamma$, starting at $i$, to reach $j$ for the first time. In particular, the quasi-metric of mean first passage time for the simple random walking on a connected unweighted graph $G$, in which there is an equal probability of moving from any vertex to any adjacent vertex, is a weighted quasi-metric, i.e., there exists a weight function $w: V\rightarrow\mathbb {R}_ {\ge 0}$, such that $ m(i,j) + w_i= m(j,i)+ w_j $ for all $i, j\in V$. We consider also some connections of the mean first passage time quasi-metric to other metric structures on graphs (in particular to $\alpha $-metric forest and its relatives), which are less studied, but not less interesting. Finally, the fifth section deals with examples of the construction of mean first passage time quasi-metrics. In addition to illustrating the "graphical" procedure of building the matrix $M$, recurrent research algorithms are presented and the resulting generalized metric structures are analyzed.

Détail

Keywords: Markov chain, mean first passage time, spanning rooted forest of an oriented graph, quasi-metric, mean first passage time quasi-metric, forest metric.

Bibliographie

[1] Deza M.M., Deza E.I., Dutour Sikirić M., “Polyhedral structures associated with quasi-metrics”, Chebyshevskii sbornik, 16:2 (2015), 79–92 | MR | Zbl

[2] Kudryashov B.D., Information Theory, Piter, StPb., 2009

[3] Potapov V., Information Theory. Coding of discrete probabilistic sources, NSU center, Novosibirsk, 1999

[4] Harari F., Graph Theory, URSS, M., 2003

[5] Shannon K., Works on Information theory and Cybernetics, IL, M., 1963

[6] Catral M., Neumann M., Xu H., “Proximity in group inverses of M-matrices and inverses of diagonally dominant M-matrices”, Linear Algebra and its Applications, 409 (2005), 32–50 | DOI | MR | Zbl

[7] Chebotarev P., A graph theoretic interpretation of the mean first passage times, 2007, arXiv: math.PR/0701359

[8] Chebotarev P., “Studying new classes of graph metrics”, Proceedings of the SEE Conference "Geometric Science of Information", GSI-2013, Lecture Notes in Computer Science, 8085, eds. F. Nielsen, F. Barbaresco, 2013, 207–214 | DOI | MR | Zbl

[9] Chebotarev P., Agaev R., “Forest matrices around the Laplacian matrix”, Linear Algebra and its Applications, 356 (2002), 253–274 | DOI | MR | Zbl

[10] Chebotarev P., Deza E., “Hitting time quasi-metric and its forest representation”, Optimization Letters, 14 (2020), 291–307 | DOI | MR | Zbl

[11] Chebotarev P. Y., Shamis E. V., “On proximity measures for graph vertices”, Automation and Remote Control, 59 (1998), 1443–1459 | MR | Zbl

[12] Chebotarev P., Shamis E., Matrix forest theorems, 2006, arXiv: 0602575v1 | MR

[13] Chebotarev P., Shamis E., The forest metric for graph verticies, arXiv: 060257v1 | MR

[14] Deza E., Deza M., Dutour Sikirić, Generalizations of Finite Metrics and Cuts, World Scientific, 2016 | MR | Zbl

[15] Deza M., Deza E., “Cones of partial metrics”, Contributions to Discrete Mathematics, 6 (2011), 26–47 | MR | Zbl

[16] Deza M. M., Deza E., Encyclopedia of Distances, Springer, Berlin–Heidelberg, 2016 | MR | Zbl

[17] Deza M., Deza E., Vidali J., “Cones of weighted and partial metrics”, Advances in Algebraic Structures, Proceedings of the Internat. Conference on Algebra (2010), 2012, 177–197 | MR | Zbl

[18] Hausdorff F., Grundzuge der Mengenlehre, Walter de Gruyter, Berlin, 1927 | MR

[19] Kirkland S. J., Neumann M., Group inverses of M-matrices and their applications, CRC Press, 2012 | MR

[20] Klein D., Zhu H., “Distances and volumina for graphs”, Journal of Mathematical Chemistry, 23 (1998), 179–195 | DOI | MR | Zbl

[21] Leighton T., Rivest R. L., The Markov chain tree theorem, Computer Science Technical Report MIT/LCS/TM-249, Laboratory of Computer Science, MIT, Cambridge, Mass., 1983

[22] Leighton T., Rivest R. L., “Estimating a probability using finite memory”, IEEE Transactions on Information Theory, 32 (1986), 733–742 | DOI | Zbl

[23] Meyer C. D. Jr., “The role of the group generalized inverse in the theory of finite Markov chains”, SIAM Review, 17 (1975), 443–464 | DOI | MR | Zbl

[24] Wentzell A. D., Freidlin M. I., “On small random perturbations of dynamical systems”, Russian Mathematical Surveys, 25 (1970), 1–55 | MR

[25] Wilson W., “On quasi-metric spaces”, American Journal of Mathematics, 53 (1931), 675–684 | DOI | MR