  Multi-agent coordination algorithms with randomized interactions have seen
use in a variety of settings in the multi-agent systems literature. In some
cases, these algorithms can be random by design, as in a gossip-like algorithm,
and in other cases they are random due to external factors, as in the case of
intermittent communications. Targeting both of these scenarios, we present
novel convergence rate estimates for consensus problems solved over random
graphs. Established results provide asymptotic convergence in this setting, and
we provide estimates of the rate of convergence in two forms. First, we
estimate decreases in a quadratic Lyapunov function over time to bound how
quickly the agents' disagreement decays, and second we bound the probability of
being at least a given distance from the point of agreement. Both estimates
rely on (approximately) computing eigenvalues of the expected matrix
exponential of a random graph's Laplacian, which we do explicitly in terms of
the network's size and edge probability, without assuming that any relationship
between them holds. Simulation results are provided to support the theoretical
developments made.
