Consensus and Products of Random Stochastic Matrices: Exact Rate for Convergence in Probability

We find the exact rate for convergence in probability of products of independent, identically distributed symmetric, stochastic matrices. It is well-known that if the matrices have positive diagonals almost surely and the support graph of the mean or expected value of the random matrices is connected, the products of the matrices converge almost surely to the average consensus matrix, and thus in probability. In this paper, we show that the convergence in probability is exponentially fast, and we explicitly characterize the exponential rate of this convergence. Our analysis reveals that the exponential rate of convergence in probability depends only on the statistics of the support graphs of the random matrices. Further, we show how to compute this rate for commonly used random models: gossip and link failure. With these models, the rate is found by solving a min-cut problem, and hence it is easily computable. Finally, as an illustration, we apply our results to solving power allocation among networked sensors in a consensus+innovations distributed detection problem.