Preprint C153/2012
Stochastic Processes over Finite Graphs

Alan Prata de Paula

**Keywords: **
Push model | Gumbel law | cover time

This PhD thesis consists of two parts, both of them related to the study of stochastic processes over
discrete structures.
In the first part we study the relation between the performance of the randomized rumor spreading
(push model) in a d-regular graph G and the performance of the same algorithm in the percolated
graph Gp. We show that if the push model successfully broadcast the rumor within T rounds in the
graph G then only $(1 + epsilon)T$ rounds are needed to spread the rumor in the graph Gp when T = o (pd).
In the second part we study the cover time C of a graph G. The expected value of C is wellunderstood
in several families of examples, but much less is known about its fluctuations. In this
paper, we give sufficient conditions under which the fluctuations of the cover time converges to the
Gumbel extreme value distribution, making progress on a well-known open problem. The distribution
of late points for the random walk is also determined under the same conditions. Our methods apply
to many “locally transient” families as discrete tori $(Z/LZ)d$ with $d geq 3$ (also proven by Belius) and
high girth expanders, as well as to all examples where Gumbel limits were previously known to hold.