  In this paper we study the influence of additive noise in randomized
consensus algorithms. Assuming that the update matrices are symmetric, we
derive a closed form expression for the mean square error induced by the noise,
together with upper and lower bounds that are simpler to evaluate. Motivated by
the study of Open Multi-Agent Systems, we concentrate on Randomly Induced
Discretized Laplacians, a family of update matrices that are generated by
sampling subgraphs of a large undirected graph. For these matrices, we express
the bounds by using the eigenvalues of the Laplacian matrix of the underlying
graph or the graph's average effective resistance, thereby proving their
tightness. Finally, we derive expressions for the bounds on some examples of
graphs and numerically evaluate them.
