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

superacid

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

白c超超

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

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

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

lulijie

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

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

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

lulijie

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

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

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

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