反射原理证明

dongzhenmao · 2026-07-12 12:27:12 · 算法·理论

在一维简单对称随机游走中，超过 2n 步仍未回到起点的概率，恰好等于第 2n 步回到起点的概率：

考虑到正面求证非常困难，我们将其转化为等价的对立事件来证明，即证明： 在 1 到 2n 步内回到过起点的概率，恰好等于第 2n 步不在起点的概率。

普通： 特殊（不类似卡特兰数的）：

一些约定：

• 游走在一维坐标轴上进行，每一步以等概率向右（+1）或向左（-1）。总步数为 2n。
• 我们将路径等效到二维网格上：把一维的向右 +1 记为网格中的向右走一步（R），向左 -1 记为向上走一步（L）。
• 游走从原点 (0,0) 开始。回到一维起点即意味着向右和向左的步数相等（x=y），也就是路径触碰对角线 y=x。
• 考虑到对称性，我们先假定所有路径的第一步都是向右的（即走到 (1,0)，记为 r 步）。
• 路径终点坐标记为 (a, b)，其中 a+b = 2n。第 2n 步回到起点意味着 a=b=n。
• 蓝色集合（等式左边）：在 1 到 2n 步内回到过起点（即途中触碰过 y=x 的路径）。
• 红色集合（等式右边）：第 2n 步不在起点（即 a \neq b 的路径）。
• 以下的举例推导均以 2n = 8 为例。

为了证明蓝红两个集合的概率（即路径总数）相等，我们在它们之间构造双射。我们将蓝色集合（触碰过 y=x 的路径）分为两类：

特殊映射：终点满足 a \le b 的蓝色路径（翻折线实际上是绿线，我懒得重画了）

第一类路径的终点 (a, b) 满足 a \le b，这意味着终点在对角线 y=x 上或其上方。 由于游走的第 1 步固定向右到了 (1,0)（处于对角线下方），而终点却跑到了对角线上方或其上。根据格路的连续性，这些路径在途中必然已经触碰过对角线 y=x，因此它们天然全部属于蓝色集合。

我们对其使用特殊映射： 保留第 1 步不变，对后续的 2n-1 步整体互换方向（即将 R 换成 L，L 换成 R）。

设原路径终点为 (a, b)，由于第 1 步向右消耗了 1 个 R，剩余的 2n-1 步中包含 a-1 个 R 和 b 个 L。 整体互换后，后续步骤变为了 b 个 R 和 a-1 个 L。 加上第 1 步的 1 个 R，新路径的终点变为：

由于原先 a \le b，显然有 a-1 < b，两边同时加 1 得到 a \le b+1，进一步推导可知 a-1 < b+1。 这意味着新的终点 (a', b') = (b+1, a-1) 必然满足 a' > b'。 这就完美地把所有 a \le b 的蓝色路径，一一对应到了红色集合中满足 a' > b' 的那一半路径上。 例如：(r, 3, 5) \to (r, 6, 2)。

普通映射：终点满足 a > b 且触碰过 y=x 的蓝色路径

第二类路径的终点 (a, b) 满足 a > b（终点在对角线下方），且途中触碰过 y=x。 这一部分属于经典的反射原理范畴。

我们对其使用普通映射： 保留第 1 步不变。找到路径第一次触碰原点线 y=x 的点，并将该触碰点之后的路径部分沿 y=x 进行翻折（即只对后半段进行 R \leftrightarrow L 互换）。

根据几何对称性，触碰点之后的路径被翻折后，原终点 (a, b) 将会关于对角线对称，变成新的终点 (b, a)。 因为我们已知原先 a > b，所以翻折后的新坐标 (a', b') = (b, a) 必然满足 a' < b'。 同时，任何落在 a' < b' 的红色路径，因为是从 (1,0) 出发的，必然也要穿过 y=x 才能到达对角线上方，因此这个映射是完全可逆的双射。 这完美地把剩下所有触碰过 y=x 的蓝色路径，一一对应到了红色集合中满足 a' < b' 的另一半路径上。 例如：(r, 5, 3) \to (r, 3, 5)。

End

综合上述两部分，我们有：

即：

而对于一个 2n 步的简单对称游走，第 2n 步恰好在起点（即向右 n 步，向左 n 步）的概率显而易见：