We study the products W k ···W 1 of random stochastic, not necessarily symmetric matrices. It is known that, under certain conditions, the product W k · · · W 1 converges almost surely (a.s.) to a random rank-one matrix; the latter is equivalent to |λ 2 (W k · · · W 1 )| → 0 a.s., where λ 2 (·) is the second largest (in modulus) eigenvalue. In this paper, we show that the probability that |λ 2 (W k · · · W 1 )| 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 W k ‘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.
