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 W_kW_k-1...W₁ of random symmetric, stochastic matrices W_k. Albeit it is known that the probability P that the product W_kW_k-1...W₁ is ∈ away from its limit converges exponentially fast to zero, i.e., P ~ e^-kI, the asymptotic rate I has not been computed before. In this paper, assuming the positive entries of Wk 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.