# 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 S_{n} the number of rounds taken until all nodes know the rumor.

Already Frieze and Grimmett (1985) give the fairly precise result that S_{n} = (1 ± o(1)) (log_{2} 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 + ε)(log_{2} n + γ ln n). The first bound was sharpened by Pittel (1987), who proved that for any h = ω(1), we have Pr(|S_{n} -log_{2} n – ln n| ≥ h(n)) → 0.

We show that S_{n} is very closely described by log_{2} n plus (1/n) times the completion time C_{n} of the coupon collector process with n coupon types: For any ε > 0, S_{n} is dominated by ⌈log_{2} n⌉ + (1 + O(n^{-1/2 + ε})) C_{n}/n + 2.562 + o(1) + Geom(1 – O(n^{-1+ε})). On the other hand, an elementary argument shows that S_{n} is subdominated by ⌊log_{2} n⌋ + (1/n) C_{n}(n/2) – 1, where C_{n}(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: ⌊log_{2} n⌋ + ln n – 1.116 ≤ E[S_{n}] ≤ ⌈log_{2} 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.