再来一个随机漫游问题

无心人

总有一部分结果会远远的不走向原位
即使走100万步
那部分是记录下数量还是怎么的？

mathe

我觉得可以抛弃掉，或者也把这个数目记录下来。不知道比例有多高？

mathe

通过Wimax计算出一个近似递推公式:
$p(n+4)=0.072438024517074695738094138263378*p(n+3)+0.13962878163821307676948451375055*p(n+2)$
$+0.26914313016882800558496745355079*p(n+1)+0.51879006367588422190745389443528*p(n)$ (这下推导出精度更加高的了)
这样是不是容易验证一些？

无心人

不知道咋的
程序似乎存在问题
每次暴力搜索一万个亿
基本不输出归零的呢
哎
上午程序在学校，懒得去拿

==================
呵呵，刚找到问题了
再重新运行下

[ 本帖最后由 无心人 于 2008-7-22 17:39 编辑 ]

无心人

你那个公式是表明当前位置的概率的么？

mathe

表示当前位置最终到达偶数点的概率

无心人

第一个结果出来了
走100000000步
有17次回零
但似乎奇偶的结果不对
呵呵

无心人

p(0)＝？

mathe

是进1退4，所以通常应该很快退回去的呀？你是不是弄反了，成进4退1了？
现在想到计算非常好的办法了，所以13#公式精度也可以提高到很高了（完全用计算器算的）
首先我们可以得到递推式$p(n+1)=2p(n)-p(n-4),n>=1$
对应特征多项式为$x^5-2x^4+1$,而这个特征方程有一个特征根$r>1$,一个特征根为1,其余特征根$x_1,x_2,x_3$绝对值小于1。
由于我们知道这个递推有界，所以如果将递推数列通项公式写成
$p(n)=u_1*r^n+u_2+v_1*x_1^n+v_2*x_2^n+v_3*x_3^n$
那么必然有$u_1=0$, 可以参考(http://bbs.emath.ac.cn/thread-354-1-1.html)
于是得到的数列的必然同样以${x^5-2x^4+1}/{x-r}$为特征多项式，而这个多项式展开后为
$x^4-(2-r)x^3-r(2-r)x^2-r^2(2-r)x-r^3(2-r)$
也就是我们有递推式$p(n+4)=(2-r)p(n+3)+r(2-r)p(n+2)+r^2(2-r)p(n+1)+r3(2-r)p(n)$
其中r为方程$x^5-2x^4+1=0$唯一大于1的解。

mathe

而为了n趋向无穷的时候，我们需要求解通项公式，我们可以假设通项公式为
$p(n)=u+v_1*x_1^n+v_2*x_2^n+v_3*x_3^n$
其中$f(x)=x^5-2x^4+1=(x-r)(x-1)(x-x_1)(x-x_2)(x-x_3)$
然后将n=0,-1,-2,-3代入，我们需要解方程组
$[(1,1,1,1),(1,x_1^-1,x_2^-1,x_3^-1),(1,x_1^-2,x_2^-2,x_3^-2),(1,x_1^-3,x_2^-3,x_3^-3)][(u),(v_1),(v_2),(v_3)]=[(1),(0),(1),(0)]$
但是这个方程不是很容易解
但是另外一个方程挺容易解的：
$[(1,1,1,1),(1,x_1^-1,x_2^-1,x_3^-1),(1,x_1^-2,x_2^-2,x_3^-2),(1,x_1^-3,x_2^-3,x_3^-3)][(y_1),(y_2),(y_3),(y_4)]=[(1),(-1),(1),(-1)]=[(1),((-1)^1),((-1)^2),((-1)^3)]$
这个根据范得蒙行列式的公式可以得到
${(y_1={(-1-x_1^-1)(-1-x_2^-1)(-1-x_3^-1)}/{(1-x_1^-1)(1-x_2^-1)(1-x_3^-1)}),(y_2={(-1-1)(-1-x_2^-1)(-1-x_3^-1)}/{(x_1^-1-1)(x_1^-1-x_2^-1)(x_1^-1-x_3^-1)}),(y_3={(-1-1)(-1-x_1^-1)(-1-x_3^-1)}/{(x_2^-1-1)(x_2^-1-x_1^-1)(x_2^-1-x_3^-1)}),(y_4={(-1-1)(-1-x_1^-1)(-1-x_2^-1)}/{(x_3^-1-1)(x_3^-1-x_1^-1)(x_1^-1-x_2^-1)}):}$
当然这个表达式还是过于复杂，但是我们注意到$h(x)=x^5-2x+1=(x-r^-1)(x-1)(x-x_1^-1)(x-x_2^-1)(x-x_3^-1)$,而且$h'(1)=(1-r^-1)(1-x_1^-1)(1-x_2^-1)(1-x_3^-1),h'(x_k)=(1-r^-1)\prod_{t!=k}(x_k^-1-x_h^-1)$
上面公式可以变化为
${(y_1={h(-1)(1-r^-1)}/{h'(1)(-1-r^-1)(-1-1)}={1-r^-1}/{3(1+r^-1)}),(y_2={h(-1)(x_1^-1-r^-1)}/{h'(x_1^-1)(-1-r^-1)(-1-x_1^-1)}),(y_3={h(-1)(x_2^-1-r^-1)}/{h'(x_2^-1)(-1-r^-1)(-1-x_2^-1)}),(y_4={h(-1)(x_3^-1-r^-1)}/{h'(x_3^-1)(-1-r^-1)(-1-x_3^-1)}):}$
于是我们知道通项公式
$b(n)=y_1+y_2*x_1^n+y_3*x_2^n+y_4*x_3^n$
得到的结果相当于如果最终结果是偶数得分为1，奇数得分为-1,那么从位置n出发得分的期望值.
于是$b(n)=p(n)*1+(1-p(n))*(-1)=2p(n)-1$,得到
$p(n)={b(n)+1}/2={y_1+1}/2+{y_2+1}/2*x_1^n+{y_3+1}/2*x_2^n+{y_4+1}/2*x_3^n$
而n趋向无穷时的极限为${y_1+1}/2={{1-r^-1}/{3(1+r^-1)}+1}/2={2r+1}/{3(r+1)}$
而通项公式基于其中$x_1,x_2,x_3$都是复数，表达式太复杂，用计算器不好算，我没有继续了