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.

Anexos:

• thesis_alan_prata.pdf