数学研发论坛

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

[转载] 随机游走中的概率问题

[复制链接]
 楼主| 发表于 2008-4-11 14:27:36 | 显示全部楼层
现在计算结果是在下面两个数之间
0.54364331210052407755147385529445
0.54364331210052407755147385529454
fr3.zip (1.97 KB, 下载次数: 2, 售价: 1 枚金币)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-11 16:12:42 | 显示全部楼层


都要钱了啊
地主家也没余粮啊

计算这么精确做什么啊?

点评

的确。下载这个附件还需要$1$块钱,让人很不爽 : ( 开玩笑而已,别当真):  发表于 2019-2-23 15:52
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-11 16:19:59 | 显示全部楼层
这样不行吗:
令P(a,b)为A赢a次,B赢b次,并且A从没超过B的概率。显然要a<b*pi
依次计算关于P(a,b)的三角数阵:
p(1,0)
p(1,1) p(2,1),p(3,1)
p(1,2) p(2,2),p(3,2),p(4,2),p(5,2),p(6,2)
........
每行有[k*pi]项
计算方法为:
if  a>b*pi 令P(a,b)=0
于是
P(a,b)=P(a-1,b)/2 +P(a,b-1)/2
然后累加满足a+b=n的项

点评

递推式中P(a-1,b)/2有点问题,既然是从未超过,那么说不定(a-1,b)之后A再走一步就超过了。  发表于 2013-12-12 18:18
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-11 16:24:34 | 显示全部楼层
可以这样去做,不过解方程的时候你会发现变量的数目总是大于解的数目。当然可以用最小二乘法去解决。
但是最大的问题是这样去做很难估计计算结果的精度。

原来无心人是超级大地主(还有余粮的地主)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-11 17:26:50 | 显示全部楼层
没看清,原来你是在求第无穷步的极限。我还以为是求第n步的呢。
你们都收钱,看来我也得整点东西卖才行。

“由于q(k)有界 (0≤q(k)≤1),而且容易证明,当k趋向无穷时,q(k)趋向0,我们马上可以得到am+1,am+2,...,am+n都是0.”
这句不理解。

评分

参与人数 1经验 +3 收起 理由
KeyTo9_Fans + 3 行~你卖的东西我要了~这是3块钱~拿好了哦~

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-11 19:38:45 | 显示全部楼层
这是因为$|x_{m+1}|>=1,....,|x_{m+n}|>=1$
比如它们中间绝对值最大的是$|x_{m+n}|$,
那么如果这一项对应系数,那么我们知道数列
$a_1 x_1^k+a_2x_2^k+....+a_{m+n} x_{m+n}^k$在k充分大时极限行为同$|a_{m+n} x_{m+n}^k|$相同
由于这个极限为0,那么只能$a_{m+n}=0$,然后同样可以得出前面几个也是0
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-11 21:19:52 | 显示全部楼层
呵呵,找到解析结果了
$q(n)=1+\prod_{k=1}^m (1-y_k)$
这下计算简单了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-12 09:54:50 | 显示全部楼层
计算很简单,只是不容易想到
记$f(x)=(x-y_1)(x-y_2)...(x-y_m)$
我们要找出通项公式
$q(k)=a_1 y_1^{-k}+a_2 y_2^{-k}+...+a_m y_m^{-k}$
而且已经知道$q(0)=q(-1)=...=q(-m+1)=1$
我们知道$f'(x)=\sum_{k=1}^{m} \prod_{h!=k} (x-y_h)$
所以$f'(y_k)=\prod_{h!=k} (x-y_h)$
然后我们通过插值定义公式
$g_k(x)=\sum_{h=0}^{m} {y_h^k f(x)}/{(x-y_h)f'(y_h)} -x^k$
对于$0<=k<=m-1$我们知道$g_k(x)$是次数不超过m-1的多项式,但是
$y_1,y_2,...,y_m$都是多项式的根,所以上面多项式都只能是0多项式
所以$g_k(1)=0$
于是我们可以得到通解
$a_k = {f(1)}/{(1-y_k)f'(y_k)}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-12 09:57:22 | 显示全部楼层
又由$g_m(x)$是m次多项式,而且$y_1,y_2,...,y_m$都是多项式的根,而且多项式最高次数项系数为-1,我们可以得到
$g_m(x)=-(x-y_1)(x-y_2)...(x-y_m)$
带入得到$g_m(1)=-(1-y_1)(1-y_2)...(1-y_m)$
由此可以得到$q(-m)=1-(1-y_1)(1-y_2)...(1-y_m)$
然后用$q(n)=2-q(-m)$就可以得到$q(n)=1+(1-y_1)(1-y_2)...(1-y_m)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-13 08:58:46 | 显示全部楼层
前面过程实际上我们还有一步需要补充证明,也就是证明$y_1,y_2,...,y_m$互不相同。
这个可以通过证明方程$x^{m+n}-2x^n+1=0$没有重根来证明。而证明函数$f(x)=0$没有重根,只需要判断
$f(x)$和$f'(x)$没有公因子就可以了,这个过程也稍微有点计算上的小技巧,这里就不写出来了,大家可以试一试看。
通过上面分析,我们知道,现在这个问题可以通过一个接近O(m)时间复杂度的算法得到。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-6-20 00:44 , Processed in 0.118191 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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