TY - GEN
T1 - Products of stochastic matrices
T2 - 2012 20th Telecommunications Forum, TELFOR 2012
AU - Bajovic, Dragana
AU - Xavier, Joao
AU - Sinopoli, Bruno
PY - 2012
Y1 - 2012
N2 - We study the products Wk···W1 of random stochastic, not necessarily symmetric matrices. It is known that, under certain conditions, the product Wk ⋯ W1 converges almost surely (a.s.) to a random rank-one matrix; the latter is equivalent to |λ2(Wk ⋯ W1)| → 0 a.s., where λ2(·) is the second largest (in modulus) eigenvalue. In this paper, we show that the probability that |λ2(Wk ⋯ W1)| stays above ε ∈ (0,1] in the long run decays to zero exponentially fast ∼ e -kI. Furthermore, we explicitly characterize the rate of this convergence I and show that it depends only on the underlying graphs that support the matrices Wk's. Our results reveal that the rate I is essentially determined by the most likely way in which the union (over time) of the support graphs fails to form a directed tree.
AB - We study the products Wk···W1 of random stochastic, not necessarily symmetric matrices. It is known that, under certain conditions, the product Wk ⋯ W1 converges almost surely (a.s.) to a random rank-one matrix; the latter is equivalent to |λ2(Wk ⋯ W1)| → 0 a.s., where λ2(·) is the second largest (in modulus) eigenvalue. In this paper, we show that the probability that |λ2(Wk ⋯ W1)| stays above ε ∈ (0,1] in the long run decays to zero exponentially fast ∼ e -kI. Furthermore, we explicitly characterize the rate of this convergence I and show that it depends only on the underlying graphs that support the matrices Wk's. Our results reveal that the rate I is essentially determined by the most likely way in which the union (over time) of the support graphs fails to form a directed tree.
KW - Consensus
KW - Convergence in probability
KW - Directed networks
KW - Exponential rate
KW - Stochastic matrices
UR - https://www.scopus.com/pages/publications/84874144307
U2 - 10.1109/TELFOR.2012.6419349
DO - 10.1109/TELFOR.2012.6419349
M3 - Conference contribution
AN - SCOPUS:84874144307
SN - 9781467329842
T3 - 2012 20th Telecommunications Forum, TELFOR 2012 - Proceedings
SP - 883
EP - 886
BT - 2012 20th Telecommunications Forum, TELFOR 2012 - Proceedings
Y2 - 20 November 2012 through 22 November 2012
ER -