求虫子爬行的步数的期望值。（公布答案）

lulijie

1。数轴的原点有一只虫子，沿着数轴往右爬行，每步随机爬行x，(x为0至n-1之间的任何一个整数，包括0和n-1)，当它的位置>=n时结束。    n为整数。
求虫子爬行的步数的期望值。
2。数轴的原点有一只虫子，沿着数轴往右爬行，每步随机爬行x，( x∈[0,1) ，x为实数)，当它的位置>=1时结束。   
求虫子爬行的步数的期望值。
－－－－－－－－－－－－－－－－－－－－－－
－－－－－－－－－－－－－－－－－－－－－－
25楼和28楼已经解出本题。本题就是采用递推数列的解法解出。
现在我总结如下：
设虫子爬行距离大于等于m所需的步数期望为f(m)

因为第一步爬行的距离为0、1、......、n-1的概率都是1/n。
那么有以下递推公式：   
    f(m)=1/n*(f(m)+f(m-1)+......+f(m-n+1))+1
设数列前m项的和为S(m)。那么上述式子可变为：
    S(m)-S(m-1)=1/n*(S(m)-S(m-n))+1
移项得   (n-1)/n*S(m)=S(m-1)-1/n*S(m-n)+1
即      S(m)=n/(n-1)*S(m-1)-1/(n-1)*S(m-n)+n/(n-1)    式子1
当m<=n时，有   S(m)=n/(n-1)*S(m-1)+n/(n-1)          式子2
解式子2的递推数列   得S(m)=n*(n/(n-1))^m-n
所以    f(m)=S(m)-S(m-1)=(n/(n-1))^m        m<=n
那么第一题所求的就是f(n)＝(n/(n-1))^n
当m>n时，要解式子1，想解出它的通项没那么容易。
        如果想用特征根的方法来解简直不可能会解出通项。
       我的想法是采用分段的方法。
      比如n<m<=2n时     m-n<=n    所以 S(m-n)=n*(n/(n-1))^(m-n)-n
        将它代入式子1，解出n<m<=2n时的通项。
      再将新的通项代入式子1，解出 2n<m<=3n时的通项。
    ...............
    分析每段通项的公式的规律，归纳出总的通项公式。
    这还只是我的想法，不知是否可行。
-------------
第二题：f(n)=(n/(n-1))^n，令n趋向无穷大，得极限为 e。
    所以第二题的答案是e。

[ 本帖最后由 lulijie 于 2009-8-19 21:57 编辑 ]

今夜微凉

来个沙发吧~这题貌似用穷举法恐怖~用概率论的东西？我猜一猜吧~第一题，2n/(n-1)，第二题，2~

[ 本帖最后由 今夜微凉 于 2009-8-16 12:36 编辑 ]

Atato

x为0至n-1之间的任何一个整数，包括0和n-1
X应该是随即取的吧...
不然谁知道是什么分布啊什么的.
---------
同意楼上的...

[ 本帖最后由 Atato 于 2009-8-16 12:35 编辑 ]

noski

第二题我算出期望值是发散的，汗：
我想，走n-1步还在[0,1)之间的概率为1/(n-1)，再走一步走出[0,1)的概率是1/2，这样，恰好n步走出[0,1)的概率P(n)就是1/(2n-2)；
期望E＝Σ(2→∞) n/(2n-2) ＝∞；
貌似我想的太简单了。。
-----------
错误答案

[ 本帖最后由 noski 于 2009-8-16 20:05 编辑 ]

yang_bigarm

可以用计算机模拟一下

superacid

貌似第二题是第一题的极限..

lulijie

哈哈，楼上说对了，只要求出第一题的表达式，让n趋向无穷大，就得到第二题的答案。
可以先用电脑模拟一下，看看n与结果有什么关系。
第二题也可模拟一下，看看是什么答案。

zxl0714

为什么我得出了一个这么复杂的公式。。。。


第2题编程模拟出来是e

[ 本帖最后由 zxl0714 于 2009-8-16 22:52 编辑 ]

lulijie

8楼：请用你的公式计算一下，n=2，n=3，n=4，...... ,期望值分别是多少？

zxl0714

2: 4.000000
3: 3.375000
4: 3.160494
5: 3.051758
6: 2.985984
7: 2.941897
8: 2.910285
9: 2.886508
10: 2.867972
11: 2.853117
12: 2.840944
13: 2.830788
14: 2.822186
15: 2.814805
16: 2.808404
17: 2.802799
18: 2.797851
19: 2.793449
20: 2.789510