CS 269S, Winter 2014: Theory Seminar
Bren Hall, Room 1423, 1pm
January 24, 2014:

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