魔方吧·中文魔方俱乐部

标题: 求虫子爬行的步数的期望值。（公布答案） [打印本页]

作者: lulijie 时间: 2009-8-16 12:18:03 标题: 求虫子爬行的步数的期望值。（公布答案）

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 编辑 ]

作者: 今夜微凉 时间: 2009-8-16 12:33:20

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

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

作者: Atato 时间: 2009-8-16 12:33:46

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

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

作者: noski 时间: 2009-8-16 14:22:04

第二题我算出期望值是发散的，汗：
我想，走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 时间: 2009-8-16 18:58:08

可以用计算机模拟一下

作者: superacid 时间: 2009-8-16 20:00:55

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

作者: lulijie 时间: 2009-8-16 20:32:03

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

作者: zxl0714 时间: 2009-8-16 22:42:03

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

第2题编程模拟出来是e

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

附件: 2.jpg (2009-8-16 22:51:00, 8.49 KB) / 下载次数 51
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NjQwNDl8OTU0NGZkMDB8MTc0MDU1MjE2N3wwfDA%3D

作者: lulijie 时间: 2009-8-16 22:48:17

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

作者: zxl0714 时间: 2009-8-16 22:54:47

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

作者: lulijie 时间: 2009-8-16 23:03:09

楼上的结果是对的，但公式太复杂了，能不能简化一下。

作者: lulijie 时间: 2009-8-16 23:24:39

从8楼的计算公式，思路应该是这样的：
2步完成，一共有多少种情况，每种情况的概率是1/n^2，
3步完成，一共有多少种情况，每种情况的概率是1/n^3，
4步完成，一共有多少种情况，每种情况的概率是1/n^4，
。。。。。。
然后将它们全部相加得到。
这是最自然的想法。不过得出的公式很复杂。
-----------------------------------------------------
有没有其他的解题思路呢？有时候换一下思路，就柳暗花明。

[ 本帖最后由 lulijie 于 2009-8-16 23:47 编辑 ]

作者: superacid 时间: 2009-8-17 15:05:52

貌似是(1+1/(n-1))^n

作者: lulijie 时间: 2009-8-17 16:31:28

楼上答案正确，如何证明呢？

作者: superacid 时间: 2009-8-17 16:43:26

我是根据数据猜出来的

[ 本帖最后由 superacid 于 2009-8-17 17:00 编辑 ]

作者: lulijie 时间: 2009-8-17 18:00:23

有一种巧妙的解题思路，可以直接解出上述的公式。

作者: zxl0714 时间: 2009-8-17 18:20:26

我只发现了f( i, j ) = ( 1 + 1 / ( i - 1 ) ) ^ j，表示n = i，位置>= j时的路线期望。。。易得f( i, 1 ) = 1 + 1 / ( i - 1 )
但是不会证后面的。。。

作者: 白c超超 时间: 2009-8-17 20:47:21

随便猜个公式

附上实验结果

[ 本帖最后由白c超超于 2009-8-17 20:59 编辑 ]

附件: S.JPG (2009-8-17 20:48:53, 10.5 KB) / 下载次数 20
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NjQxMTh8ZGM5ZTkyYTJ8MTc0MDU1MjE2N3wwfDA%3D

附件: S1.PNG (2009-8-17 20:59:08, 4.73 KB) / 下载次数 22
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NjQxNDl8OGY2OGMwOTh8MTc0MDU1MjE2N3wwfDA%3D

作者: superacid 时间: 2009-8-17 21:00:17

楼上这个公式能化简一下吗？

作者: 白c超超 时间: 2009-8-17 21:04:44 标题: 回复 19# 的帖子

不会，这个只是前面公式的简化版。。

再附上我同学用Mathematica算的答案

[ 本帖最后由白c超超于 2009-8-17 21:16 编辑 ]

附件: S3.jpg (2009-8-17 21:16:03, 4.6 KB) / 下载次数 26
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NjQxNTF8NTg2ZDkyOWZ8MTc0MDU1MjE2N3wwfDA%3D

作者: superacid 时间: 2009-8-17 21:22:23

我们要想一种简单的办法，而不是通过很烦的算式算出来，这样就没意思了。

作者: 白c超超 时间: 2009-8-17 21:28:02

这条公式已经简化很多了。

不过也要想想是不是有更好的思路。

作者: tm__xk 时间: 2009-8-18 01:56:56

每步可走1,2,...,n-1.
当再走k就结束时,仍需的步数期望设为a[k].(这句话说得不太好,希望能看懂....)
只需求a[n].

已知a[1]=1.
易知递推式为a[k]=Σa/(n-1)+1,1<=i<=k-1.
设S[k]=Σa,1<=i<=k,则S[k]=S[k-1]*n/(n-1)+1
==>S[k]=n*(n/(n-1))^(k-1)-n+1
==>a[k]=S[k]-S[k-1]=(n/(n-1))^(k-1)
==>所求期望a[n]=(n/(n-1))^(n-1)

[ 本帖最后由 tm__xk 于 2009-8-18 22:56 编辑 ]

作者: lulijie 时间: 2009-8-18 21:45:46

23楼思路非常正确，解题技巧也很对头，但审题没审清楚。
我说的每步可爬行0,1,2,......,n-1 ，包括0。

作者: Cielo 时间: 2009-8-18 22:32:42

递推式也许是下面这样？
a[sub]k[/sub]=(1/n)Σ[sub]i=1[/sub][sup]k[/sup]a[sub]i[/sub] + (n-k)/n
————————————————————————————————
搞错了，递推的时候应该多一步，后面加的确实是 1 而不是 (n-k)/n.

这样的话，a[sub]k[/sub] = [n/(n-1)][sup]k[/sup] 吧？

[ 本帖最后由 Cielo 于 2009-8-18 23:15 编辑 ]

作者: tm__xk 时间: 2009-8-18 22:50:21

汗死........修改下....

初项改为a[1]=2.
递推式改为a[k]=Σa/n+1,1<=i<=k.
设S[k]=Σa,1<=i<=k,则S[k]=S[k-1]*n/(n-1)+n/(n-1)
==>S[k]=(n+2)*(n/(n-1))^(k-1)-n
==>a[k]=S[k]-S[k-1]=(n+2)/(n-1)*(n/(n-1))^(k-2)
==>所求期望a[n]=(n+2)/(n-1)*(n/(n-1))^(n-2)

继续修改....见28L....

[ 本帖最后由 tm__xk 于 2009-8-18 23:38 编辑 ]

作者: lulijie 时间: 2009-8-18 22:58:58

回楼上，a(1)不等于2。

作者: tm__xk 时间: 2009-8-18 23:36:28

继续汗....我把概率写错了....笔误....
继续修改....

初项改为a[1]=n/(n-1).
==>S[k]=(n/(n-1)+n)*(n/(n-1))^(k-1)-n=n*(n/(n-1))^k-n
==>a[k]=S[k]-S[k-1]=(n/(n-1))^k
==>所求期望a[n]=(n/(n-1))^n

希望这次没错....

作者: lulijie 时间: 2009-8-18 23:46:50

25楼和28楼，现在对了。
这道题就是用递推来算，非常简单。
那么增加难度：
--------------------------
数轴的原点有一只虫子，沿着数轴往右爬行，每步随机爬行x，(x为0至n-1之间的任何一个整数，包括0和n-1)，当它的位置>=m时结束。 n、m为整数。
求虫子爬行的步数的期望值f(m)。
当m<=n时，f(m)=(n/(n-1))^m
那么，当m>n时，有没有通项公式呢？

作者: tm__xk 时间: 2009-8-19 00:23:18

同理,稍微修改下递推公式就行了..
常系数线性递归数列....
通项公式可以有....
不过....你先把(n-1)*x^n-n*x^(n-1)+1=0这个关于x的方程解出来........
PS.不排除我还算错..不过肯定是n次的....

作者: lulijie 时间: 2009-8-19 22:05:57

楼上采用特征根的方法解递推数列，本题对于n不定的情况下，很难能解出通项公式

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)