条件化有向图的平稳分布能否在小空间内近似？

κ-条件化同时约束混合速度与平稳质量

该算法并不适用于任意有向图。它要求游走矩阵 W 满足 κ-条件化，这包含两项彼此独立的承诺。第一，平稳分布 s(W) 必须接近均匀分布：对每个顶点 i 都有 1/(κn) ≤ s(W)_i ≤ κ/n。第二，链必须是 κ-混合的，即 W^κ 的每个元素与秩一矩阵 s(W)1ᵀ 的对应元素相差不超过 n⁻¹⁰。

这两个条件承担不同作用。平稳质量界防止目标向量集中在少数顶点上，从而使相对误差成为有意义的目标。混合界保证游走在 κ 步之后已经忘记起点，这正是构造能够用一条短且性质良好的矩阵链替代长游走的原因。论文把这一设定视为通往“随机对数空间是否等于确定性对数空间”这一未解问题的中间问题。

空间界取决于 log²κ 而非游走长度

定理 1.1 指出，对每个固定常数 c > 0，存在一个确定性算法：给定 n、整数 1 < κ ≤ n，以及对一个 n 顶点、常数度出正则、游走矩阵为 κ-条件化的有向图的邻接表访问，算法输出估计值 ŝ₁, …, ŝₙ，满足对每个顶点 i 有 |ŝᵢ − s(W)ᵢ| ≤ n⁻ᶜ s(W)ᵢ，使用 O((log n + log²κ) log log n) 比特工作空间。

误差是相对的而非加性的：每个估计值都与该顶点自身的平稳概率比较，并按 n⁻ᶜ 缩放。空间开销由 log n 与 log²κ 主导，再乘以一个 log log n 因子。当 log κ ≤ √log n 时，该界退化为 O(log n log log n)，与论文所依托的欧拉图游走估计结果同阶。对 κ 的依赖正是该结果区别于一般有向图算法的关键，后者的空间界直接包含游走长度。

改进只在一个特定的 κ 区间成立

论文所做的比较对象，是一般有向图中近似 κ 步随机游走的最好已知界，由 Hoza（RANDOM 2021）给出，使用 O(log n √log κ / √log log n) 空间。新界仅在 κ = exp(Θ(log^α n)) 且 α 在 (0, 2/3) 内的区间优于该界。

在该区间之外，比较结果并不自动有利于新算法，论文也没有这样声称。这一收益还伴随着额外假设：Saks–Zhou 与 Hoza 的一般图算法不需要任何混合或平稳分布承诺，而本结果同时需要 κ-条件化的两半。论文明确陈述了这一权衡，因此该改进应被理解为以图满足 κ-条件化承诺为前提，而不是有向图的普遍加速。

修剪在平方过程中维持行质量有界

该构造把去随机化平方与一个修剪过程结合起来。去随机化平方反复用提升后的、经扩展图平均的平方替换游走矩阵，从而在各层级上几何式地压低近似误差。问题在于，ℓ₂ 型近似误差并不控制行和：平方后矩阵的入度质量可能膨胀，一旦膨胀，朴素的去随机化平方就会失效。

修剪通过从超出预算的行中删除质量、并把删除的质量归还到对角线上来解决这一问题，同时保持列随机性。一维分析表明，修剪后的矩阵行质量保持在 (α + β)1 以内，并且只引入有界的一侧误差。论文指出的困难在于，朴素修剪需要平方对数空间，因为它要运行很多轮；作者通过只做部分修剪、并同步协调平方与修剪步骤来应对，这正是把总体空间重新压下来的原因。

稳定化需要 O(log_κ n + log κ) 轮

二维链通过稳定化轮 r_max 来分析，它是最小的轮数，此后每一层的原始矩阵、删除矩阵与修剪矩阵都不再变化。引理 5.4 把它界定为 O(log_κ n + log κ)。一个保守论证先给出 O(log n log κ) 轮，其思路是重行每轮缩小 κ 倍，直到不再有重行。

更紧的界来自关于不稳定行数的递推式 u(t, r) ≤ poly(κ, log n) u(t−1, r) + κ⁻¹ u(t, r−1)，初始条件为 u(t, 0) ≤ n|L_t|。求解得到 u(t, r) ≤ n(4K)^t κ^{−r/2}，当 r 超过约 2 log_κ n 再加上一个 log κ 项时，该值在每一层都降到 1 以下。这个轮数决定了最终的空间核算：递归深度为 O(log n + (T + r_max)h)，代入 T = O(log κ) 与稳定化界，就得到 O((log n + log²κ) log log n) 的总量。

游走概率经由欧拉化归约得到

推论 1.2 把平稳分布结果扩展到单个游走概率。给定顶点 i、j 与整数 1 ≤ k ≤ poly(n)，它输出估计值 p̂，满足 |p̂ − (W^k)_{ij}| ≤ n⁻ᶜ，使用同样的 O((log n + log²κ) log log n) 比特工作空间。

该归约通过重新加权实现。近似平稳向量 ŝ 被用来构造失衡向量 b = Wŝ − ŝ，再加入一个修正项，形成一个行和与列和相等的加权邻接矩阵 F，从而使其成为欧拉图。所得转移矩阵与 W 之间的扰动在 ℓ₁ 范数下被界定为 8δ，对 k 步做望远镜求和后，总游走概率误差仍在预算之内。随后由 Ahmadinejad 等人的欧拉图游走估计算法给出估计。需要注意，该推论继承了定理 1.1 的 κ-条件化假设；它并不是关于任意有向图的陈述。

预印本状态限制了可核查的范围

论文以预印本形式发布，作者直接说明了原因：近期有关于相关问题上基于 LLM 的进展的传闻，以及这些结果何时出现尚不确定。作者还指出，进一步的实现细节将在后续版本中提供，因此当前文本应被理解为对算法思想及其分析的陈述，而不是一份完整指定的实现。

LLM 使用声明记载，9 月 7 日作者把主要定理陈述与初始证明思路提示给 GPT-6 Astra，模型提供了关键算法思想，包括修剪过程与同步分析。手稿由作者基于自己对所得算法的理解完成，GPT Codex 与 Devin.AI 在检查、重新排版以及部分论述与证明的起草和修订上提供了协助。对权衡该结果的读者而言，实际后果是：空间界与改进区间是需要对照证明仔细审视的部分，而实现层面的主张仍被推迟。

决定性问题是 κ-条件化是否成立

阅读这篇论文最有用的方式，是把它看作一笔有条件的权衡。如果一个有向图同时满足 κ-条件化的两半——平稳概率在因子 κ 内接近均匀，且 κ 步混合在逐元素意义上达到 n⁻¹⁰ 以内——那么平稳分布可以在随 log²κ 而非随游走长度增长的空间内被近似到逆多项式相对误差。如果图不满足这些承诺，该结果就不适用，相关比较就回到一般有向图的界。

在 κ-条件化设定之内，需要检查的具体阈值是 κ = exp(Θ(log^α n)) 且 α 在 (0, 2/3) 内的区间。正是在这里，新的 O((log n + log²κ) log log n) 界优于一般有向图中 κ 步游走的 O(log n √log κ / √log log n) 界。论文自身的定位把该结果视为解决随机对数空间是否等于确定性对数空间的中间一步，因此这一改进的价值应依据具体应用的图是否真的落在该 κ 区间内来判断。

本文引用的文献