Exact Rate for Convergence in Probability of Averaging Processes via Generalized Min-Cut

We study the asymptotic exponential decay rate I for the convergence in probability of products WkWk-1...W1 of random symmetric, stochastic matrices W-k. Albeit it is known that the probability P that the product WkWk-1...W1 is epsilon away from its limit converges exponentially fast to zero, i.e., P similar to e(-kI), the asymptotic rate I has not been computed before. In this paper, assuming the positive entries of W-k are bounded away from zero, we explicitly characterize the rate I and show that it is a function of the underlying graphs that support the positive (non zero) entries of W-k. In particular, the rate I is given by a certain generalization of the min-cut problem. Although this min-cut problem is in general combinatorial, we show how to exactly compute I in polynomial time for the commonly used matrix models, gossip and link failure. Further, for a class of models for which I is difficult to compute, we give easily computable bounds: I <= I <= I, where I and I differ by a constant ratio. Finally, we show the relevance of I as a system design metric with the example of optimal power allocation in consensus+innovations distributed detection.