×

Triangulated Laman graphs, local stochastic matrices, and limits of their products. (English) Zbl 1462.15036

Summary: We derive conditions on the products of stochastic matrices guaranteeing the existence of a unique limit invariant distribution. Belying our approach is the hereby defined notion of restricted triangulated Laman graphs. The main idea is the following: to each triangle in the graph, we assign a stochastic matrix. Two matrices can be adjacent in a product only if their corresponding triangles share an edge in the graph. We provide an explicit formula for the limit invariant distribution of the product in terms of the individual stochastic matrices.

MSC:

15B51 Stochastic matrices
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
40A20 Convergence and divergence of infinite products
52C25 Rigidity and flexibility of structures (aspects of discrete geometry)
60J05 Discrete-time Markov processes on general state spaces
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Wolfowitz, J., Products of indecomposable, aperiodic, stochastic matrices, Proc. Am. Math. Soc., 14, 5, 733-737 (1963) · Zbl 0116.35001
[2] Chatterjee, S.; Seneta, E., Towards consensus: some convergence theorems on repeated averaging, J. Appl. Probab., 89-97 (1977) · Zbl 0381.60056
[3] Daubechies, I.; Lagarias, J. C., Sets of matrices all infinite products of which converge, Linear Algebra Appl., 161, 227-263 (1992) · Zbl 0746.15015
[4] Lorenz, J., A stabilization theorem for dynamics of continuous opinions, Phys. A, Stat. Mech. Appl., 355, 1, 217-223 (2005)
[5] Bolouki, S.; Malhamé, R. P., On consensus with a general discrete time convex combination based algorithm for multi-agent systems, (2011 19th Mediterranean Conference on Control & Automation (MED) (2011), IEEE), 668-673
[6] Touri, B., Product of Random Stochastic Matrices and Distributed Averaging (2012), Springer Science & Business Media · Zbl 1244.15023
[7] Chevalier, P.-Y., Convergent products of stochastic matrices: Complexity and algorithms (2018), Université catholique de Louvain, Ph.D. thesis
[8] Kolmogoroff, A., Zur theorie der markoffschen ketten, Math. Ann., 112, 1, 155-160 (1936) · JFM 61.0563.03
[9] Graver, J. E.; Servatius, B.; Servatius, H., Combinatorial Rigidity, Vol. 2 (1993), American Mathematical Soc. · Zbl 0788.05001
[10] Chen, X.; Belabbas, M.-A.; Başar, T., Global stabilization of triangulated formations, SIAM J. Control Optim., 55, 1, 172-199 (2017) · Zbl 1354.93010
[11] Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D., Randomized gossip algorithms, IEEE Trans. Inf. Theory, 52, 6, 2508-2530 (2006) · Zbl 1283.94005
[12] He, F.; Morse, A. S.; Liu, J.; Mou, S., Periodic gossiping, IFAC Proc. Vol., 44, 1, 8718-8723 (2011)
[13] Liu, J.; Mou, S.; Morse, A. S.; Anderson, B. D.; Yu, C., Deterministic gossiping, Proc. IEEE, 99, 9, 1505-1524 (2011)
[14] Liu, Y.; Li, B.; Anderson, B. D.; Shi, G., Clique gossiping, IEEE/ACM Trans. Netw., 27, 6, 2418-2431 (2019)
[15] Chen, X.; Belabbas, M.-A.; Liu, J., Gossip over holonomic graphs, submitted for publication · Zbl 1480.93018
[16] Wang, X.; Mou, S.; Sundaram, S., A resilient convex combination for consensus-based distributed algorithms, Numer. Algebra Control Optim., 9, 3, 269 (2019) · Zbl 1451.68349
[17] Blackwell, D., Finite non-homogeneous chains, Ann. Math., 594-599 (1945) · Zbl 0063.00421
[18] Doob, J. L., Kolmogorov’s early work on convergence theory and foundation, Ann. Probab., 17, 3, 815-821 (1989) · Zbl 0687.01008
[19] Hajnal, J.; Bartlett, M. S., Weak Ergodicity in Non-homogeneous Markov Chains, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 54, 233-246 (1958), Cambridge University Press · Zbl 0082.34501
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.