步长随机的行走问题

无心人

我不知道linux下的随机小数如何做的

mathe

Linux下面的是31比特，其实你输出RAND_MAX就可以知道了。

mathe

呵呵，运行速度够慢的，我试了将运行次数加了10被 对于n=2输出4.670680

无心人

是比较慢 可是没办法啊 如果用更好的随机数程序 还要慢的 另外，似乎用 rand / (RAND_MAX + 1.0) 更好些 不知道结果如何

无心人

n = 1000 2000.664773

mathe

我用(rand()+0.5)/(1.0+RAND_MAX)

mathe

我们记 $E(n,s,h)=\int...\int_{ {: (s-1<=\sum_{i=1}^n x_i<=s),(0<=x_i<=1):} } {(s-\sum_{i=1}^n x_i)^h}/{h!}dx_1dx_2...dx_n$,其中在$n>=s>=1,h>=0$时有定义,而对于定义外面的所有$E(n,s,h)$我们定义为0, 而且我们知道$E(1,1,h)=1/{(h+1)!}$ 那么行走n+1步才超过距离$S,(S>=1)$的概率可以写成 $\sum_{s=1}^S(E(n,s,0)-E(n+1,s,0))$,也就是n步还小于s,但是n+1步大于s了. 而我们现在要计算的期望步数为 $P(S)=\sum_{s=1}^S\sum_{n=s}^{infty} (n+1)(E(n,s,0)-E(n+1,s,0))$ 定义特征函数 $F_{s,h}(x)=\sum_{n=s}^{infty} (E(n,s,h)-E(n+1,s,h))x^{n-s}$ 现在我们计算$E(n,s,h)$,首先对$x_n$进行积分,为此,我们可以将积分区域分成两种情况,分别为$s-2<=\sum_{i=1}^{n-1}x_i<=s-1$和$s-1<=\sum_{i=1}^{n-1}x_i<=s$,得到 $E(n,s,h)=E(n-1,s,h+1)+1/{(h+1)!}E(n-1,s-1,0)-E(n-1,s-1,h+1)$ $E(n,s,h)-E(n+1,s,h)=E(n-1,s,h+1)-E(n,s,h+1)+1/{(h+1)!}(E(n-1,s-1,0)-E(n,s-1,0)-(E(n-1,s-1,h+1)-E(n,s-1,h+1))$ 两边乘上$x^{n+1-s}$然后对n进行求和,可以得到 $F_{s,h}(x)=x*F_{s,h+1}(x)+1/{(h+1)!}*F_{s-1,0}(x)-F_{s-1,h+1}(x)$ 另外我们知道$\lim_{h->infty}E(n,s,h)=0$,所以$\lim_{h->infty}F_{s,h}(x)=0$

mathe

由于$E(1,1,h)=1/{(h+1)!}$,$E(n,1,h)=E(n-1,1,h+1)$,我们可以得出$E(n,1,h)=1/{(h+n)!}$ 所以$F_{1,h}(x)=\sum_{n=1}^{infty}(1/{(h-1+n)!}-1/{(h+n)!})x^{n-1}$ 利用$P(1)=(F_{1,0}'(x)+F_{1,0}(x))|_{x=1}$代入可以得到 $F_{1,0}(x)=e^x-{e^x-1}/x,F_{1,0}'(x)=e^x+{e^x-xe^x-1}/{x^2}$ 所以$P(1)=(e-1)+e-(e-1)=e$

mathe

另外通过上面函数递推式以及$lim_{h->infty}F_{s,h}(x)=0$,我们可以得到 $F_{s,h}(x)=F_{s-1,0}(x)\sum_{k=0}^{infty}{x^k}/{(h+1+k)!}-\sum_{k=0}^{infty}x^k F_{s-1,h+1+k}(x)$

mathe

下面计算还是很复杂呀