Para receber por e-mail novas publicações de Seminário de Probabilidade e Combinatória, Clique Aqui!

Seminários do IMPA

Probabilidade e Combinatória

Mixing time of PageRank surfers and other regenerating walks on sparse digraphs
Pietro Caputo

Università Roma 3
Quarta-feira, 6 de novembro de 2019, 15:30
Sala 232

Given a directed graph $G$, $\alpha\in(0,1)$ and a distribution $\lambda$ over the vertices of $G$, the generalised PageRank surf on $G$ is the Markov chain on the vertices of $G$ such that at each step with probability $\alpha$ the state is updated with an independent sample from $\lambda$, while with probability $1-\alpha$ the state is moved to a uniformly random vertex in the out-neighbourhood of the current state. The stationary distribution is the so-called PageRank vector. We analyse convergence to stationarity of this Markov chain when $G$ is a large sparse random digraph with given degree sequences, in the limit of vanishing parameter $\alpha$. We identify three scenarios: when $\alpha$ is much smaller than the inverse of the mixing time of $G$ the relaxation to equilibrium is dominated by the simple random walk and displays cutoff behavior; when $\alpha$ is much larger than the inverse of the mixing time of G on the contrary one has pure exponential decay with rate $\alpha$; when $\alpha$ is comparable to the inverse of the mixing time of $G$ there is a mixed behaviour. This trichotomy holds uniformly in the starting point and for a large class of $λ$. Finally, we discuss similar trichotomies for the mixing of regenerating dynamic digraphs. Joint with Matteo Quattropani.