On the mean square error of randomized averaging algorithms

Paolo Frasca, Julien M. Hendrickx

    Research output: Contribution to journalArticleAcademicpeer-review

    10 Citations (Scopus)
    9 Downloads (Pure)


    This paper considers randomized discrete-time consensus systems that preserve the average ‘‘on average’’. As a main result, we provide an upper bound on the mean square deviation of the consensus value from the initial average. Then, we apply our result to systems in which few or weakly correlated interactions take place: these assumptions cover several algorithms proposed in the literature. For such systems we show that, when the network size grows, the deviation tends to zero, and that the speed of this decay is not slower than the inverse of the size. Our results are based on a new approach, which is unrelated to the convergence properties of the system.
    Original languageUndefined
    Pages (from-to)2496-2501
    Number of pages6
    Issue number8
    Publication statusPublished - 2013


    • EWI-24139
    • IR-88294
    • METIS-300233

    Cite this