随机游走 · Elea Notes

一句话

一个人站在一条笔直的路上，每一步靠抛硬币决定往前还是往后。他会走到哪里？答案有两半：他离原点的距离按 $\sqrt{n}$ 增长（走一万步只离一百步远），但他几乎必然一次又一次回到出发点。

如果硬币不公平——比如八成往前——第二半就彻底翻转：他以概率 1 漂向一侧，再也不回头。下面把这两句都算出来。

先看一个麻烦：走一万步能走多远

深夜的路灯下，一个喝多了的人站在马路中间。他还能走，但方向已经不受控制：每一步是往东还是往西，全凭偶然，两个方向各一半可能。

他一晚上走了一万步。请问他现在离路灯多远？

第一反应大概是”说不准”。但这个问题有确切答案，而且答案很反直觉：大约一百步。 一万步的体力，换来一百步的位移。

这个”说不准”里藏着好几个不同的问题，它们的答案彼此矛盾得厉害：他最可能在路灯底下、一步都没挪；但他大致会离一百步远；他会走回路灯下，而且会回去很多次；可要是路面有点坡、让他往东的概率变成 0.55，他就基本不会再回来了。

“最可能在原点”和”通常离一百步远”怎么同时成立？把 0.5 改成 0.55 这么小的一动，怎么会让”必然回来”变成”再也不回来”？这些不是文字游戏，每一条都能算出数来。

朴素尝试与失败

招数一：算平均位置。 每步的期望位移是 $0.5 \times (+1) + 0.5 \times (-1) = 0$ 。一万步加起来，期望位置是 0。

结论正确，但没用。它说的是”如果让一万个醉汉同时走，他们的位置平均下来是路灯”。这对任何单个醉汉都毫无预测力——一半人在东边，一半人在西边，平均值落在中间的空地上，那里恰恰没人。正负相消把要找的东西消掉了。

招数二：那就算平均距离，取绝对值。 方向对了。但绝对值在数学上难对付（ $|x|$ 不可导，也不好展开），一旦要处理两步、三步的叠加就卡住。

招数三：先算距离的平方，再开根号。 这一招能走通。平方消掉了正负号，而且对加法友好。走 $n$ 步后位置 $S_n = X_1 + \cdots + X_n$ ，每个 $X_i$ 是 $\pm 1$ 。展开平方：

S_n^2 = \sum_i X_i^2 + \sum_{i \ne j} X_i X_j

第一项：每个 $X_i^2 = 1$ （不管往哪走，平方都是 1），共 $n$ 项，贡献 $n$ 。第二项： $i \ne j$ 时两步独立， $X_iX_j$ 取 $\pm 1$ 各一半可能，期望 0，整项消失。于是

E[S_n^2] = n, \qquad \sqrt{E[S_n^2]} = \sqrt{n}

一万步， $\sqrt{10000} = 100$ 。那个根号是这套东西的签名，它的意思是位移和步数不成正比：步数翻四倍，距离只翻两倍。

  步数 n        典型距离 √n     距离/步数
       4            2.00        0.500000
     100           10.00        0.100000
   10000          100.00        0.010000
 1000000         1000.00        0.001000

走得越久，效率越低。这是没有方向偏好所付的代价。

机制：四步能走到哪，全部列出来

四步走完，一共 $2^4 = 16$ 条路径，每条概率 1/16。按”往前的步数”分类，用组合数一数：

 往前步数 k │ 位置 2k-4 │ 路径数 C(4,k) │ 概率
 ──────────┼───────────┼───────────────┼──────────
     0     │    -4     │       1       │ 1/16 = 0.062500
     1     │    -2     │       4       │ 4/16 = 0.250000
     2     │     0     │       6       │ 6/16 = 0.375000
     3     │    +2     │       4       │ 4/16 = 0.250000
     4     │    +4     │       1       │ 1/16 = 0.062500
                       └── 合计 16 ────┴── 合计 1.000000

从这张小表就能验证前面的所有结论：

 E[位置]   = (-4)(1/16)+(-2)(4/16)+0(6/16)+2(4/16)+4(1/16) = 0.000000
 E[位置²]  = 16(1/16)+4(4/16)+0+4(4/16)+16(1/16)           = 4.000000  ← 正好等于 n
 √4 = 2，而位置只能是 -4,-2,0,2,4 —— 典型距离 2，符合

“最可能在原点”和”典型距离 2”同时成立，这就是答案：0 这一格概率 0.375000，确实是单个位置里最高的；但落在 $\pm 2$ 的合计是 0.500000，落在 $\pm 4$ 的是 0.125000。分布的峰在中心，质量却铺开在两侧。所谓”平均离多远”问的是铺开的宽度，“最可能在哪”问的是峰在哪儿。两个问题，两个答案。

注意那一列路径数 1, 4, 6, 4, 1——这是杨辉三角的第四行。走 $2m$ 步正好落回原点的概率就是 $\binom{2m}{m}/2^{2m}$ ，而它下降得极慢，按 $1/\sqrt{n}$ 降，不是指数降：

  步数 n │ 第 n 步恰好在原点        │ n 步内至少回过一次
  ───────┼─────────────────────────┼──────────────────
     2   │ 2/4        = 0.500000   │      0.500000
     4   │ 6/16       = 0.375000   │      0.625000
    10   │ 252/1024   = 0.246094   │      0.753906
    14   │ 3432/16384 = 0.209473   │      0.790527
   100   │              0.079589   │      0.920411
  1000   │              0.025225   │      0.974775

慢到什么程度？慢到把所有步数上的机会加起来总和发散，于是回到原点这件事必然发生，而且必然发生无穷多次。

一条真实的轨迹（30 步，* 是所在位置，虚线是原点）：

   +1 │                         *
    0 │*═══*═══════════════════*═*═══*
   -1 │ * * *                 *   * *
   -2 │  *   * *     *       *     *
   -3 │       * *   * *     *
   -4 │          * *   *   *
   -5 │           *     * *
   -6 │                  *
      └───────────────────────────────
       0    5   10   15   20   25   30  ← 第几步

  步序：--++---+---+++----+++++++---++
  15 步往上，15 步往下，终点回到 0
  途中经过原点的时刻：第 0、4、24、26、30 步

这条轨迹很典型：它在 $-6$ 到 $+1$ 之间晃，长时间待在原点一侧（第 4 步到第 24 步一直在负半边），然后又荡回来。“一半时间在东、一半时间在西”是不对的——随机游走喜欢长时间待在一侧，这是它最容易被误解的性质。

跑十万条 100 步的轨迹，把统计量和理论值对一下（Python random.seed(20260731)，可复现）：

  平均终点位置      +0.0019    理论 0
  终点位置的均方根  10.0213    理论 √100 = 10
  平均 |终点位置|    7.9873    理论 √(2n/π) = 7.9788
  至少回过原点一次   0.9201    理论 0.920411
  终点恰好在原点     0.0800    理论 0.079589
  |终点| 超过 20     0.0352    准确值 0.035200

均方根那一行是全表的重点：它落在 10 附近，而不是 100 附近。走一万步只离原点一百步，就是这条规律在 $n = 10000$ 上的读数。

把硬币掰弯：有偏游走

现在让往前的概率变成 $p = 0.9$ 、往后 $q = 0.1$ 。每步的期望位移不再是 0，而是 $p - q = 0.8$ ，这个数叫漂移。 $n$ 步后漂移贡献 $0.8n$ ，而随机起伏仍然只有 $\sqrt{n}$ 量级（准确说是 $\sqrt{4npq}$ ）：

  n      漂移 = 0.8n     起伏 = √(4npq)     漂移/起伏
    10        8            1.8974            4.2
   100       80            6.0000           13.3
  1000      800           18.9737           42.2

漂移按 $n$ 长，起伏按 $\sqrt{n}$ 长，比值越拉越大。这就是”以概率 1 漂向一侧”的机制：走得越久，随机性越不可能翻盘。 一条从 2 出发的有偏轨迹：

  +16 │                    *
  +14 │                  *
  +12 │                *
  +10 │              *
   +8 │            *
   +6 │        * *
   +4 │    * *
   +2 │*  *
   +1 │ *
    0 │═════════════════════  ← 一旦触到 0 就出局
      └─────────────────────
       0    5    10   15  20  ← 第几步

  步序：-+++-++++-++++++++++
  17 步往上，3 步往下；第 1 步就掉到 1，险些出局
  终点 16；理论期望终点 = 2 + 20×0.8 = 18.0

第一步就差点触到 0——危险全在开局。之后漂移接管，轨迹一路走高，再没回来过。从 2 出发永远触到 0 的概率只有 $(1/9)^2 = 0.0123457$ ；要是它当时真从 1 掉到 0，游戏就已经结束了。这个 $(q/p)^z$ 正是赌徒破产问题的结论。

回访：走一步和抛一次硬币是同一件事

每一步”往前或往后”就是一次抛硬币。所以随机游走不过是把一串独立的二元结果累加起来看。这一点把它和另外两个概念钉在了一起：

泊松分布同样从”一串独立二元试验”出发，但它问的是固定窗口里发生了几次，不做累加。两者是同一堆硬币的两种读法。这也是为什么杨辉三角会出现在上面那张四步表里——组合数 $\binom{n}{k}$ 是二项分布的骨架，随机游走的位置分布就是把二项分布平移拉伸一下。
赌徒破产问题问的正是这条轨迹会不会碰到某个边界。 $(q/p)^z$ 之所以是指数形式，根源就在有偏游走的漂移是线性增长的。

比特币白皮书第 11 节的第一句话，就是把攻防写成随机游走：

诚实链与攻击者链之间的竞赛可以刻画为一个二项随机游走。成功事件是诚实链被延长一个区块，其领先优势加 1；失败事件是攻击者的链被延长一个区块，差距减 1。

对应关系是逐项的：轨迹上的位置就是诚实链领先的区块数；每一步就是全网出下一个区块的那一刻；往上一步的概率 $p$ 是诚实节点先找到区块的概率，往下一步的概率 $q$ 是攻击者先找到的概率。而 $p$ 、 $q$ 由算力占比决定——这是工作量证明提供的那一环，它把”算力份额”翻译成”每步的概率”，从而让整件事进入这个模型。

于是三个概念在这一节里各就各位：随机游走给出运动的形式，赌徒破产给出”攻击者从落后 $z$ 处追上”的闭式解 $(q/p)^z$ ，泊松分布补上”收款方不知道攻击者已经暗中挖了多少”这个不确定性。

这也说明了”确认数”为什么有效。等 $z$ 个确认，就是要求攻击者的轨迹从 $-z$ 爬回 0。只要诚实算力占多数，漂移方向就是背着攻击者的，而漂移线性、起伏只有平方根——每多一个确认，代价乘一个固定倍数。这是随机游走的几何性质，不是谁定的规则。

边界与常见误解

一维和二维必然回归，三维不。 一维对称游走以概率 1 无穷多次回到原点，二维也是；三维不成立，返回概率约 0.34，有约 2/3 的可能一去不返。波利亚 1921 年证明了这件事，常被总结成”迷路的人总能回家，迷路的鸟回不了家”。

“必然回到原点”不等于”很快回到原点”。 概率 1 说的是终究会。返回所需步数的期望是无穷大——上表里 1000 步内返回的概率是 0.974775，剩下那 0.025 的轨迹可能要走极久。概率 1 和期望有限是两件事。

不存在”该转向了”。 连着往东走了 10 步，第 11 步往西的概率还是 0.5。每步独立，硬币没有记忆。所谓”平均法则会把它拉回来”是错的：拉回来的不是绝对位置，而是每步的比例——往东的步数占比趋于 0.5，但东西步数之差可以无限增大。这两件事同时成立，也是赌本有限的人会输光的原因。

$\sqrt{n}$ 是典型尺度，不是上限。 “一万步走一百步远”说的是量级，不是禁止走更远。 $n = 100$ 时终点绝对值超过 $2\sqrt{n} = 20$ 的准确概率是 0.035200（把二项分布该求的项直接加起来），上面模拟给出 0.0352。正态近似给的 0.045500 偏大，因为它没处理位置只能取偶数这件事。 $\sqrt{n}$ 是宽度，不是边界。

有偏游走的危险集中在开局。 从落后 $z$ 处追平的概率是 $(q/p)^z$ ， $z$ 稍大就塌成极小的数。这意味着有偏游走的意外几乎只发生在最初若干步，一旦漂移积累起来，起伏就再也翻不动局面。白皮书那句”如果他没能在早期一跃而前，随着落后加深，机会就微乎其微了”，说的正是这件事。

一句话