:)
我不知道linux下的随机小数如何做的
Linux下面的是31比特，其实你输出RAND_MAX就可以知道了。
呵呵，运行速度够慢的，我试了将运行次数加了10被
对于n=2输出4.670680
:)
是比较慢
可是没办法啊
如果用更好的随机数程序
还要慢的
另外，似乎用 rand / (RAND_MAX + 1.0) 更好些
不知道结果如何
n = 1000
2000.664773
我用(rand()+0.5)/(1.0+RAND_MAX)
我们记
$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$
由于$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$
另外通过上面函数递推式以及$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)$
下面计算还是很复杂呀