4.02.2015: Talk of Prof. Dr. Benjamin Dörr
Prof. Dr. Benjamin Dörr, Laboratoire d’Informatique (LIX), Ecole Polytechnique de Paris, held a talk about “Tight Analysis of Randomized Rumor Spreading in Complete Graphs”.
Abstract:
We present a very tight analysis of the basic randomized rumor spreading process introduced by Frieze and Grimmett. The process starts with a single node of a fully connected network knowing a rumor. Then, in each round of the process, each node knowing the rumor gossips the rumor to a node chosen uniformly at random. Denote by Sn the number of rounds taken until all nodes know the rumor.
Already Frieze and Grimmett (1985) give the fairly precise result that Sn = (1 ± o(1)) (log2 n + ln n) with probability 1 – o(1). They also prove that for all ε, γ > 0, with probability at least 1 – o(nγ), the broadcast time does not exceed (1 + ε)(log2 n + γ ln n). The first bound was sharpened by Pittel (1987), who proved that for any h = ω(1), we have Pr(|Sn -log2 n – ln n| ≥ h(n)) → 0.
We show that Sn is very closely described by log2 n plus (1/n) times the completion time Cn of the coupon collector process with n coupon types: For any ε > 0, Sn is dominated by ⌈log2 n⌉ + (1 + O(n-1/2 + ε)) Cn/n + 2.562 + o(1) + Geom(1 – O(n-1+ε)). On the other hand, an elementary argument shows that Sn is subdominated by ⌊log2 n⌋ + (1/n) Cn(n/2) – 1, where Cn(n/2) is the random variable describing the time needed to collect the last n/2 coupons in the coupon collector process.
These bounds in particular give the first bound for the expected runtime of the process that is tight apart from additive constants: ⌊log2 n⌋ + ln n – 1.116 ≤ E[Sn] ≤ ⌈log2 n⌉ + ln n + 2.765 + o(1).
These results, while sounding complicated and technical, are in fact natural and not very difficult to prove. This is joint work with Marvin Künnemann (MPI Informatics, Saarbrücken.