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)$.