随机游走中的概率问题

shshsh_0510

呵呵，不好意思，还是没懂：

原帖由 mathe 于 2008-4-11 19:38 发表
这是因为$|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次方程的m个根呀？这个怎么求？也能O(m)吗？

mathe

我在前面的链接中给出一个迭代的方法，也就是可以每个点从$2^{-m}$开始迭代就可以了。
而迭代需要的次数决定于计算所要达到的精度，在计算精度给定的情况下，迭代次数基本上应该是常数，所以可以说求解的时间复杂度也是O(m)

mathe

原帖由 shshsh_0510 于 2008-4-15 14:32 发表
呵呵，不好意思，还是没懂：

就不能几个复根总是相互抵消？另外，由于复分析不懂，你那个儒歇定理看着很神奇，需要抓紧学习了！
主要的疑惑还在于：是不是得先求那个m+n次方程的m个根呀？这个怎么求？也能O(m)吗 ...

关于几个复根可以相互抵消的问题，的确是我一个疏漏，需要说明一下不可能，好像也挺难证明的。但是直觉上肯定不行。

mathe

这个问题我将它单独列出来作为一个数学题了:
http://bbs.emath.ac.cn/thread-354-1-1.html

zgg___

按照mathe的方法，可以求出p(m/n)，其中m<=n且均为正整数，由此定义函数p(x)，函数的定义域为(0,1]的有理数。（就象是mathe在4层的定义。）我们可以做出函数图像如图（n不大于50的情况。）假设有理数是稠密的，我们用某种方法来“描”，目的是把p(x)连成“曲线”。通过观察，我们可以看到p(x)在许多点是不连续的（比方说1/2-的值和1/2+的值相差很大）。那么这个函数曲线的间断点是有限的么？在间断点的值怎么取呢？是每一个有理点都是间断点么？这个函数的值域是什么呢？推推这个问题……

如图

mathe

不错的观察
我觉得应该是在所有有理点都是间断，而所有无理点都是连续的，这个可以通过这个概率模型问题去理解

shshsh_0510

这样啊？一直没时间再好好考虑这个，看来还很有意思

到处瞎逛

从mathe的签名搜索到这个帖子，有点意思。

采用13#的一步一步往下算的方法弄出来了的图像。也没做什么生成函数啊，计数方法之类的思考。

左边的是1-4对应的概率，图像一个阶梯。右边的图像是pi每一步计算概率的结果的趋近的图像，收敛的不是很快。

到处瞎逛

修改了一下文件，运行起来快多了，几乎感觉不到等候，估计是毫秒级的计算时间。
由于mathcad的精度限制，只能运算17位精度。

用mathcad的符号运算功能，精度倒是高了，速度下去了。

求得0.54364331210052407755147385529445657831392612256947034053879247246

65位

到处瞎逛

不错的观察
我觉得应该是在所有有理点都是间断，而所有无理点都是连续的，这个可以通过这个概率模型问题去理解
mathe 发表于 2008-4-24 18:00

我理解为无理数在运算的取整的过程中不会出现0这个状态，所以是连续的，有理数则不然。