找回密码
 欢迎注册
楼主: mathe

[转载] 步长随机的行走问题

[复制链接]
发表于 2008-9-4 18:01:22 | 显示全部楼层


我不知道linux下的随机小数如何做的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-4 18:52:23 | 显示全部楼层
Linux下面的是31比特,其实你输出RAND_MAX就可以知道了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-4 18:59:38 | 显示全部楼层
呵呵,运行速度够慢的,我试了将运行次数加了10被
对于n=2输出4.670680
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-4 19:48:42 | 显示全部楼层


是比较慢
可是没办法啊
如果用更好的随机数程序
还要慢的

另外,似乎用 rand / (RAND_MAX + 1.0) 更好些
不知道结果如何
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-5 07:57:44 | 显示全部楼层
n = 1000
2000.664773
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-5 08:58:16 | 显示全部楼层
我用(rand()+0.5)/(1.0+RAND_MAX)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-5 09:00:48 | 显示全部楼层
我们记
$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$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-5 09:46:10 | 显示全部楼层
由于$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$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-5 09:51:46 | 显示全部楼层
另外通过上面函数递推式以及$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)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-5 10:13:33 | 显示全部楼层
下面计算还是很复杂呀
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 18:02 , Processed in 0.043224 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表