转子路由行走对随机游走的单点占据偏差：小图族上精确极值常数的穷举测定与公式证明

1 · 研究问题

在星图、双星、圈及带弦圈等参数化小图族上，转子路由行走（rotor-router walk / Propp machine）的单点占据频率相对随机游走期望的最坏情形偏差 K(G)（对全部转子初始配置与时间取上确界）的精确值是多少？是否随族参数有封闭公式？

2 · 研究背景与空白

转子路由是随机游走的去随机化：每个顶点按固定循环序轮流指派出边。Holroyd–Propp（2010）证明命中频率、命中时间与占据频率都集中于随机游走期望附近，且偏差界与图的结构量相关；Cooper–Spencer 证明 Z^d 上单点偏差为常数 c_d（c₁ ≈ 2.29 已知）；Kijima 等（Random Struct. Alg. 2015）给出一般有限图 O(mn) 界，并知某些网格设定下偏差可无界。

空白在已有文献几乎全是渐近阶或上界，具体小图族的精确极值常数没有系统表；本轮检索未见（未找到不等于不存在，第 2 周以 exact rotor walk discrepancy small graphs 复查）。适合学生：状态空间有限可穷举、随机游走侧期望有线性代数精确解、差异轴是把"评价维度"从渐近界换成精确常数——正是文献综述里承认缺失的层面。

历届对照：2024 年金奖用马尔可夫决策过程做投掷策略、2021 年优胜研究渗透下界，说明离散概率题材有受众；两者与去随机化偏差无重叠。

3 · 可检验假设

• H1：星图 S_k 与双星族的 K 有关于度参数的显式公式（预期与最大命中时间同阶），可由数据猜出并证明。
• H2：顶点数 ≤ 6 的全部连通图上，K(G) 与最坏命中时间之比落在可证明的常数区间内。

4 · 量化验收标准

1. 方法学校验（硬门槛）：(a) 在 Z 的有限截断上复现 Cooper–Spencer 常数 c₁ ≈ 2.29 至 3 位有效数字；(b) 随机游走占据期望用线性方程组精确解与 10^7 步蒙特卡洛对比，偏差 < 3σ。任一不过则后续无效。
2. 穷举表：n ≤ 6 的全部 112 个连通图，对全部转子初始配置（∏ deg(v) ≤ 6^6 ≈ 4.7×10^4 每图，含旋转序选择）与时间窗算出精确 K(G)；时间窗截断须附收敛判据（偏差序列进入周期轨道的检测）。
3. 结构化族（星/双星/圈）参数推到 n ≤ 50，公式与数据 100% 吻合，并对至少一族完成证明。
4. 统计口径：所有蒙特卡洛对照报标准误；确定性穷举结果为精确有理数/整数，不涉及抽样误差。
5. 模拟器与表格开源。

5 · 数据与工具

用途	来源 / 工具
转子模拟器	Python 自写（无现成库；networkx 仅用于图生成与同构去重）；单步 O(1)，10^9 步/小时量级单核
随机游走精确期望	numpy/sympy 解线性方程组（占据期望、命中时间的标准一次方程）
图库	networkx graph_atlas_g（内置 n ≤ 7 全部图）
已知界对照	Holroyd–Propp 2010、Kijima 2015 的界——仅对比用，不计入贡献

6 · 方法路径

1. 写模拟器与精确期望求解器，完成两项校验。
2. 核实"偏差过程最终周期化"的理论依据（转子系统状态有限 ⟹ 最终周期），据此写出可证明的时间窗截断判据。
3. 穷举 n ≤ 6 全图全初值，建 K(G) 精确表。
4. 对星/双星/圈扫参数，猜公式。
5. 用位势函数/雅可比恒等式证明所猜族公式（Holroyd–Propp 的 odometer 技术可复用）。
6. 交叉校验：族公式与穷举表在交集逐点一致；抽样图用暴力长时模拟复核上确界未被低估。

7 · 新颖性边界

概念、集中性与 O(mn) 界均为已发表结果（Holroyd–Propp 2010；Cooper–Spencer；Kijima 等 2015），本项目不声称任何渐近改进。贡献（主结论）：小图与小族上的首个精确极值常数表 + 至少一族封闭公式，差异轴是评价维度的转换（渐近界 → 精确常数）。价值：精确常数揭示界的紧度——若某族 K 远小于 O(mn) 界，即定量指出现有界的松弛程度；"界是紧的"同样是有效结论。

8 · 决策门槛（go / no-go）

• 第 4 周末：校验通过 + 周期化截断判据成文。判据写不出则改为"固定 10^7 步 + 双倍步长稳定性检验"的工程判据并如实报告。
• 第 9 周末：若全初值穷举在 n = 6 爆炸（部分图 ∏deg 过大）→ 降级一：初值限均匀转子 + 随机抽样 10^4 初值给下界，表格改标"下界表"，框架不变。
• 第 22 周末：族公式证明卡住 → 降级二：主结论为精确表 + 数据驱动猜想 + 单调性部分引理。
• 选择前提：需要学生接受"证明工具（odometer/位势函数）要现学"；纯计算产出已足以成文，但上限取决于证明部分。

---