#
Tight Analysis of Randomized Rumor Spreading in Complete Graphs

##
Zach Becker

Presenting a paper by Benjamin Doerr, Marvin Kunnemann

Abstract:
We present a tight analysis of the basic randomized rumor spreading
process in complete graphs introduced by Frieze and Grimmett (1985),
where in each round of the process each node knowing the rumor gossips
the rumor to a node chosen uniformly at random. The process starts
with a single node knowing the rumor.
We show that the number $S_n$ of rounds required to spead a rumor in a
complete graph with $n$ nodes is very closely described by $log_2 n$
plus $(1/n)$ times the completion time of the coupon collector
process. This in particular gives very precise bounds for the expected
runtime of the process, namely $\lfoor \log_2 n \rfloor + \ln n -
1.116 \le E[S_n] \le \lceil \log_2 n \rceil + \ln n + 2.765 + o(1)$.