请求解读Feller《概率论及其应用》中随机游走的相关推导（含投票定理）

没问题！我来帮你捋清楚这段关于随机游走的推导逻辑，先把关键符号和核心内容理得明明白白：

核心符号定义 #

• 针对长度为$n$的随机游走序列（每个步长仅为$+1$或$-1$）：
  • $p$：序列中$+1$的步数，$q$：序列中$-1$的步数，必然满足 $n = p + q$
  • $N_{n,x}$：所有$n$步后到达位置$x$的路径总数，本质是从$n$个位置里选$p$个放$+1$的组合数，也就是 $N_{n,x} = \binom{n}{p} = \binom{n}{q}$。这里的$x$是游走终点，对应关系是$x = p - q$，结合$n=p+q$，能推导出$p = \frac{n+x}{2}$、$q = \frac{n-x}{2}$，这也是$N_{n,x}$能同时用$p$或$q$表示的原因。
  • 补充个小细节：你写的$S_n=p+q$应该是笔误吧？Feller里通常$S_n$是前$n$步的游走和，也就是$S_n = p - q = x$，这个小地方注意下就行～

你提到的关键结论推导 #

设$n$和$x$为正整数，恰好有$\frac{x}{n} N_{n,x}$种……

虽然你没写完，但这个式子大概率是指从原点出发、$n$步后到达$x$，且过程中从未回到原点的路径数（或者是首次到达$x$的路径数），核心推导依赖Feller里反复用到的反射原理：

1. 先确定所有$n$步到$x$的路径总数：就是$N_{n,x} = \binom{n}{\frac{n+x}{2}}$，前提是$n+x$得是偶数，不然路径数直接为0。
2. 用反射原理计算不符合条件的路径数：比如那些过程中回到过原点的路径，通过把第一次回到原点前的路径做反射变换，能一一对应到另一种路径（比如从$-1$出发到$x$的路径），算出这类路径的数量。
3. 用总数减去不符合的数量，最终就能得到$\frac{x}{n} N_{n,x}$这个简洁的结果。

举个直观的小例子验证下：当$n=3$，$x=1$时，$p=2$、$q=1$，$N_{3,1}=\binom{3}{2}=3$，$\frac{x}{n}N_{n,x}=1$——对应的就是那条全程没回到原点的路径：$+1, +1, -1$，另外两条路径（$+1,-1,+1$、$-1,+1,+1$）都在过程中回到过原点，完全符合这个数值～

内容的提问来源于stack exchange，提问作者user13