【悬赏】波利亚酒鬼回家定理的证明

【悬赏】波利亚酒鬼回家定理的证明

诚如frankjia1986所言，在百度上问这种难度的问题是需要碰运气的。这个问题从技术上讲确实并不困难，关键在于要借助E(酒鬼处于原点的次数)，把这个期望记成m。定义u=P(酒鬼会回到原点)，u_n=P(酒鬼回到原点恰好n次)=(1-u)u^{n-1}，那么m=sum n*u_n=1/(1-u)，所以讨论u和讨论m是一回事。再定义v_n=P(n步后酒鬼处在原点)，那么m=sum v_n=sum v_{2n}，因为奇数步不可能返回。而对于2n步随机游走，当且仅当在第k个维度方向上正负各走了a_k步才能回到原点，根据多项式定理可以得到v_{2n} = 1/(2d)^{2n} * sum_{a_1+a_2+...+a_d=n} (2n)!/[a_1!a_2!...a_d!]^2。d=1,2的时候可以算出通项并用Stirling公式估计出m=+oo；而d>2的时候直接取最大的项来证明m有限。至于m具体的值是多少，我建议你编程序算。