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

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

lulijie

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

tm__xk

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

lulijie

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

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

初项改为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

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

tm__xk

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

初项改为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 编辑 ]

Cielo

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

这样的话，a_k = [n/(n-1)]^k 吧？

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

lulijie

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

tm__xk

每步可走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 编辑 ]