Averaging Over General Random Networks

This technical note studies the distributed averaging problem over general random networks, by means of augmenting state space. A general iterative scheme (with a certain structure) is proposed that is discrete-time, linear, and stochastic; its generality compared to the literature lies in that the weight matrices corresponding to the networks need not be column-stochastic, and the random process generating the update matrices need not be ergodic or i.i.d. It is then justified that the scheme achieves average consensus in the mean-square sense, which, in a special case, also implies averaging with probability one. A key technique to the justification is a matrix perturbation result, which describes the behavior of eigenvalues perturbed simultaneously by multiple parameters.