论文标题
稀疏随机有向图的最小固定值
Minimum stationary values of sparse random directed graphs
论文作者
论文摘要
我们考虑具有有限度的有向配置模型上简单随机步行的固定分布。只要最低级别至少为$ 2 $，概率很高（WHP），则具有独特的固定分配。我们表明，对于某些常数$ c \ ge 0 $，由学位分布确定的最小正固定值为whp $ n^{ - （1+c+o（1））} $。尤其是$ c $是两个因素的竞争组合：（1）非典型“薄”内居民的贡献，由亚临界分支过程控制； （2）非典型“光”轨迹的贡献，受较大的偏差率函数控制。此外，我们的证明意味着击中和封面时间都是$ n^{1+c+o（1）} $。我们的结果补充了Caputo和Quattropani的结果，他们表明，如果最小值至少为2个，则固定值在$ n^{ - 1} $左右的对数波动会产生对数波动。
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 \ge 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}$.
