d维简单随机游走习题1.17验证：d=3,n=1是否为反例？

设$S_n$表示$d$维简单随机游走，$R_n^1,\ldots,R_nd$表示每个分量上的步数。证明对所有$n>0$，$R_{2n}^{1,\ldots,R_{2n}}d$全为偶数的概率为$2^{-(d-1)}$。这是否是一个反例？

先验证题目给出的反例（d=3, n=1） #

咱们先把这个具体例子拆解开算清楚：

• 3维空间里的2步简单随机游走，每一步有3个分量（x、y、z）可选，总共有$3^2=9$种等概率的路径。
• 要满足所有$R_2^1, R_2^2, R_2^3$全为偶数，意味着每个分量的步数只能是0或2（毕竟总步数只有2）。只有当两步都选同一个分量时，才会出现一个分量步数为2、其余为0的情况，这样的路径共有3种（两步都选x、都选y、都选z）。
• 计算概率：$3/9=1/3$，但按照题目里的结论$2^{-(3-1)}=1/4$，显然不相等——这说明原命题的结论是错误的，这个例子就是一个实打实的反例。

正确的概率推导思路 #

那正确的概率该怎么算？我们可以用组合计数+生成函数的思路来推导：

1. 总路径数：每一步有$d$种选择，$2n$步总共有$d^{2n}$种等概率路径。
2. 满足条件的路径数：每个分量的步数$R_{2n}^{i=2k_i$（$k_i$为非负整数），且$\sum_{i=1}}d k_i = n$。对于每组这样的$k_1,\dots,k_d$，对应的路径数是多项式系数$\binom{2n}{2k_1, 2k_2, \dots, 2k_d} = \frac{(2n)!}{(2k_1)! (2k_2)! \dots (2k_d)!}$。
3. 生成函数筛选偶数项：利用离散傅里叶变换的正交性，满足条件的总路径数可以表示为：
   $$\frac{1}{2^d} \sum_{s_1=\pm1} \dots \sum_{s_d=\pm1} (s_1 + s_2 + \dots + s_d)^{2n}$$
   代入d=3,n=1验证：所有符号组合共8种，计算总和为$9+3+3+9=24$，除以$2^3=8$得到3，正好和我们之前数出的满足条件的路径数一致，概率$3/9=1/3$。

原结论的适用范围？ #

原结论说概率是$2^{-(d-1)}$，其实只在少数情况成立，比如d=2时：

• d=2,n=1，2步游走总路径数$2^{2=4$，满足条件的路径有2种（两步都选x或都选y），概率$2/4=1/2=2}{-(2-1)}$，确实符合结论。但d≥3时就不成立了，这也说明原命题的结论并不具有普遍性。

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