随机游走中的概率问题

mathe

现在计算结果是在下面两个数之间 0.54364331210052407755147385529445 0.54364331210052407755147385529454 fr3.zip (1.97 KB, 下载次数: 2, 售价: 1 枚金币)

2008-4-11 14:30 上传

点击文件名下载附件
阅读权限: 20

无心人

都要钱了啊 地主家也没余粮啊 计算这么精确做什么啊？

shshsh_0510

这样不行吗： 令P(a,b)为A赢a次，B赢b次,并且A从没超过B的概率。显然要ab*pi 令P(a,b)=0 于是 P(a,b)=P(a-1,b)/2 +P(a,b-1)/2 然后累加满足a+b=n的项

mathe

可以这样去做，不过解方程的时候你会发现变量的数目总是大于解的数目。当然可以用最小二乘法去解决。 但是最大的问题是这样去做很难估计计算结果的精度。 原来无心人是超级大地主（还有余粮的地主）

shshsh_0510

没看清，原来你是在求第无穷步的极限。我还以为是求第n步的呢。 你们都收钱，看来我也得整点东西卖才行。 “由于q(k)有界 (0≤q(k)≤1)，而且容易证明，当k趋向无穷时,q(k)趋向0,我们马上可以得到am+1,am+2,...,am+n都是0.” 这句不理解。

mathe

这是因为$|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

mathe

呵呵，找到解析结果了 $q(n)=1+\prod_{k=1}^m (1-y_k)$ 这下计算简单了。

mathe

计算很简单,只是不容易想到
记$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)}$

mathe

又由$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)$

mathe

前面过程实际上我们还有一步需要补充证明，也就是证明$y_1,y_2,...,y_m$互不相同。
这个可以通过证明方程$x^{m+n}-2x^n+1=0$没有重根来证明。而证明函数$f(x)=0$没有重根，只需要判断
$f(x)$和$f'(x)$没有公因子就可以了，这个过程也稍微有点计算上的小技巧，这里就不写出来了，大家可以试一试看。
通过上面分析，我们知道，现在这个问题可以通过一个接近O(m)时间复杂度的算法得到。