6.856 — Randomized Algorithms
(b) From (a) we know that the expected time until some machine is successful is Θ(e). Since the problem is symmetric in all n machines, the successful machine is equally likely to be any of the machines. This is also true for the next successful machine, and so on. So the question is how long it takes for all machines to be successful, if every Θ(e) steps, a random machine is successful. This is just the coupon collectors problem: we expect Θ(n ln n) successful broadcasts before every machine actually sent their first packet. So the expected time for all machines to be successful is Θ(ne ln n).