Minimum stationary values of sparse random directed graphs

10/14/2020
by   Xing Shi Cai, et al.
0

We consider the stationary distribution of the simple random walk on the directed configuration model with bounded degrees. Provided that the minimum out-degree is at least 2, with high probability (whp) there is a unique stationary distribution. We show that the minimum positive stationary value is whp n^-(1+C+o(1)) for some constant C ≥ 0 determined by the degree distribution. In particular, C is the competing combination of two factors: (1) the contribution of atypically "thin" in-neighbourhoods, controlled by subcritical branching processes; and (2) the contribution of atypically "light" trajectories, controlled by large deviation rate functions. Additionally, our proof implies that whp the hitting and the cover time are both n^1+C+o(1). Our results complement those of Caputo and Quattropani who showed that if the minimum in-degree is at least 2, stationary values have logarithmic fluctuations around n^-1.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset