完全图上具有有界边通过时的尾达渗流

来源：应用数学学报杂志2025年第5期北京时间：

作者：郭亚蒙, 王峰, 吴宪远

单位：首都师范大学数学科学学院, 北京 100048

摘要：考虑完全图$G_{n}=\big([n],E_{n}\big)$上的尾达渗流模型. 记$W_n$ 为经自回避路从顶点$1$ 到顶点$n$ 的最长通过时间, $\mu$为模型的时间常数, 即边通过时$X_e$的本质上界(本文研究$\mu<\infty$的情形, 不失一般性, 我们假设$\mu=1$). 本文研究$W_n$的次阶, 即$n-W_n$随$n$的增长情况. 确切地, 对$X_e$的尾概率$\mathbb P(X_e>x)$不衰减、幂律衰减和指数衰减三种情形, 我们首先给出$n-\mathbb E(W_n)$的上下界估计; 进而通过估计$W_n$的方差, 给出$n-W_n(=o(n))$的上界估计.

关键词：完全图,尾达渗流,贪婪算法,方差估计