MIXING AND COVER TIME ON SPARSE RANDOM DIGRAPHS

Abstract

In my thesis I investigate some properties of random walks on sparse ran dom directed graphs. The topic is quite new to the probabilistic community, and few results are present in the recent literature. In particular, the thesis will be composed of three preprints. The first work concerns the mixing behavior of the PageRank surfer on sparse random digraph. Such a Markov chain can be thought of as a random walk in which at each time step there is a small chance to be reset with a given distri bution. Algebraically, the transition matrix of the walk is simply a rank-one perturbation of the transition matrix of the simple random walk on the same digraph. We show the same set of results on two different underlying random geometries: the so called out-configuration model (OCM) and the directed configuration model (DCM), which are the two most natural generalization to the directed setting of the well-studied (undirected) configuration model (CM). In particular, we show that the mixing behavior of the chain undergoes a phase-transition depending on the order of magnitude of the perturbation. The techniques we use are an extension of the ones developed by Bordenave, Caputo and Salez, [2], [3]. In the second work we analyze some extremal properties of the DCM en semble and of the random walk on such random digraphs. In particular, we give sharp with-high-probability bounds on the diameter of the digraph, on the extremal values of the stationary distribution and on the cover time. This last paper is more technical and requires a mixture of tools, among which: coupling arguments, martingale approximations and a law of large numbers 1 for paths weights. The third and last work constitutes the first (toy) example in the proba bilistic literature of the analysis of the mixing behavior of a random walk on a (randomly) evolving random digraph. The results are in the same vein of [1], in particular we show that a phase-transition similar to the one in [1] takes place in this model. All the results we derive in this work are valid both in the DCM and in the OCM setup.