Please use this identifier to cite or link to this item: http://hdl.handle.net/2307/40879
Title: MIXING AND COVER TIME ON SPARSE RANDOM DIGRAPHS
Authors: QUATTROPANI, MATTEO
Advisor: CAPUTO, PIETRO
LOPEZ, ANGELO FELICE
Keywords: RANDOM GRAPHS
MIXING TIME
Issue Date: 27-Apr-2020
Publisher: Università degli studi Roma Tre
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.
URI: http://hdl.handle.net/2307/40879
Access Rights: info:eu-repo/semantics/openAccess
Appears in Collections:Dipartimento di Matematica e Fisica
T - Tesi di dottorato

Files in This Item:
File Description SizeFormat
PhD-thesis-MQ.pdf1.1 MBAdobe PDFView/Open
SFX Query Show full item record Recommend this item

Page view(s)

6
checked on Nov 26, 2022

Download(s)

2
checked on Nov 26, 2022

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.