Trichotomy phenomena in the mixing of sparse digraphs

Vienna Probability Seminar

I will present some recent results concerning the mixing time of simple stochastic processes on configuration-like models of sparse random digraphs. In particular, I will focus on two examples: the PageRank dynamics and the simple random walk on a regenerating digraph. In both examples the stationary distribution is a non-trivial object, in contrast to the setting in which the underlying graph is undirected. Moreover, in both cases the relaxation to the equilibrium state is given by the interplay of two different mechanisms. I will show that it is possible to tune the interaction between the two mechanisms in order to obtain three different asymptotic behaviors for the total variation distance. In particular, if the interaction is taken so that both the mechanisms compete on the same time scale, the total variation distance will exhibit a peculiar discontinuity. This is a joint work with P. Caputo.