再来一个随机漫游问题

无心人

总有一部分结果会远远的不走向原位 即使走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$都是复数，表达式太复杂，用计算器不好算，我没有继续了