华新 - 一个数学题

一个数学题有1到N连续的N个自然数，从中随机抽取m个数（1<=m<=N)，问这m个数中最大数的Expected Value是多少？第二大数呢？第t个数呢（1<=t<=m，t=1表示最小数，t=m表示最大数)？[大树下 (5-12 15:28, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

re好久没学概率了,试着回答一下,思路是:

设最大数为Z,则Z的取值范围应该是[m,N]

设随机抽取的m个数为x1,x2,...xm,则Z=x(x在[m,N]区间内) 的概率为x1<=x同时x2<=x,...,xm<=x,(同时也要考虑每个数只能取一次)
[baoxin (5-12 16:19, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

抽出的数能不能一样？换句话，抽了一个放回去再抽下一个，还是不放回去？[吴永铮 (5-12 19:09, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼

(引用吴永铮:抽出的数能不能一样？换句话，抽了一个放回去再抽下一个，还是不放回去？)忘了说了，这m个数互不重复，即每个数最多只能取一次[大树下 (5-13 10:10, Long long ago)] [ 传统版 | sForum ][登录后回复]4楼

(引用 baoxin:re好久没学概率了,试着回答一下,思路是: 设最大数为Z,则Z的取值范围应该是[m,N] 设随机抽取的m个数为x1,x2,...xm,则Z=x(x在[m,N]区间内...)仔细想了一下,偶这个解答好像不对[baoxin (5-13 10:53, Long long ago)] [ 传统版 | sForum ][登录后回复]5楼

回答,见内[baoxin (5-13 11:45, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼

(引用 baoxin:回答,见内)图片没贴上

[baoxin (5-13 11:48, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼

(引用 baoxin:图片没贴上 ...)方向没错，不过式子可以简化的，最后的结果很简洁[大树下 (5-13 14:16, Long long ago)] [ 传统版 | sForum ][登录后回复]8楼

这样n个数里面抽出m个数，那么还剩下n-m个数，这n-m个数被切成了m+1段(允许段的长度为0)。如果知道这m+1段，每一段的期望值d(k), 1<=k<=m+1，那么这道题就做出来了。因为最大的数就是n-d(m+1)，第t个数为1+d(1)+1+d(2)+...+1+d(t)。要说明一点，期望值可以随意相加减，不用顾忌是否互相独立。E(X+Y)=E(X)+E(Y)

我们可以通过对称来求d(k)。不要把这n个数想成线段，而把他们想成首尾相连的一个圆环，那么这段圆环被切为m段，而非m+1段。首尾没有特殊性了，每段都是平等的。由于对称，这m段的期望值因该是一样的。他们的和是n-m，那么期望值都等于(n-m)/m。现在再把这个圆环从一个地方拆开，恢复到线段。因为是任意选一点拆的，所以首尾两端的期望值为其他的一半，即(n-m)/(2m)。那么d(1)=d(m+1)=(n-m)/(2m); d(2)=d(3)=...=d(m)=(n-m)/m

那么现在就只需要带入就行了。最大的数为n-(n-m)/(2m)=(2mn-n+m)/(2m)，第t个数为1+d(1)+1+d(2)+...+1+d(t)=(m+n+2tn-t)/(2m)[吴永铮 (5-16 1:38, Long long ago)] [ 传统版 | sForum ][登录后回复]9楼

(引用吴永铮:这样n个数里面抽出m个数，那么还剩下n-m个数，这n-m个数被切成了m+1段(允许段的长度为0)。如果知道这m+1段，每一段的期望值d(k), 1...)没看懂没看懂你的意思。我问的是抽出的m个数中某个数（最大数，最小数...第t个数）的期望值，为什么你要把剩下的n-m个数分成m+1段？这个每段的期望值跟m个数中最大的数的期望值没有直接的联系吧。[大树下 (5-16 21:06, Long long ago)] [ 传统版 | sForum ][登录后回复]10楼

(引用大树下:没看懂没看懂你的意思。我问的是抽出的m个数中某个数（最大数，最小数...第t个数）的期望值，为什么你要把剩下的n-m个数分成m+1段？这个�...)比如n=100，m=2，抽出的数是30和50那么30和50把[1,100]分成3(即m+1)段：[1,29],[31-49],[51-100]，这三段的长度为98(即n-m)。

如果第一段的长度期望值为29，那么最小数的期望值就是30。之间的联系就是这样。[吴永铮 (5-17 13:04, Long long ago)] [ 传统版 | sForum ][登录后回复]11楼

(引用吴永铮:这样n个数里面抽出m个数，那么还剩下n-m个数，这n-m个数被切成了m+1段(允许段的长度为0)。如果知道这m+1段，每一段的期望值d(k), 1...)上面的方法有错，圆环不应切为m段，而应该是m+1段正确方法应该是：长度为n-m的圆环被随机切为m+1段。每一段长度期望值为(n-m)/(m+1)。之前提到的d(k)=(n-m)/(m+1)，与k无关。

所以最小数期望值为1+d(1)=1+(n-m)/(m+1)=(n+1)/(m+1)，第t小的为1+d(1)+1+d(2)+...+1+d(t)=t*(1+(n-m)/(m+1))=(tn+t)/(m+1)[吴永铮 (5-18 15:20, Long long ago)] [ 传统版 | sForum ][登录后回复]12楼

(引用吴永铮:上面的方法有错，圆环不应切为m段，而应该是m+1段正确方法应该是：长度为n-m的圆环被随机切为m+1段。每一段长度期望值为(n-m)/(m+1)。之�...)明白了把取出的数字转化成长度来考虑，这样因为是随机抽取的关系，那m+1段长度相等就没有疑问了。嗯，挺有创意的思考方式。偶像就是偶像。不过不应该再称之为圆环了吧，而是一条总长为n的线段。

据说这个叫做神扣理论，但是在网上google了一番，没找到该理论。[大树下 (5-20 10:13, Long long ago)] [ 传统版 | sForum ][登录后回复]13楼

(引用大树下:明白了把取出的数字转化成长度来考虑，这样因为是随机抽取的关系，那m+1段长度相等就没有疑问了。嗯，挺有创意的思考方式。偶像就是偶像�...)我的证明方法纯粹从概率的角度，所以比吴兄的方法复杂一些。 t等于某一个数k的概率为Combin(k-1,t-1)xCombin(n-k,m-t)/Combin(n,m),即从小于k的数中（有k-1个数）抽取t-1个数，并从大于k的数中（有n-k个数）抽取m-t个数的组合个数比上从n个数中抽取m个数的组合个数，所以P(t)的期望值是

[大树下 (5-20 11:26, Long long ago)] [ 传统版 | sForum ][登录后回复]14楼

(引用大树下:明白了把取出的数字转化成长度来考虑，这样因为是随机抽取的关系，那m+1段长度相等就没有疑问了。嗯，挺有创意的思考方式。偶像就是偶像�...)我以前做过一道类似的题，可以说是这道题的连续版在一个周长为1公里的环形山上有两个补给站，补给站是随机选取的。现在考察队在环形山上随机一个地方迷失方向，于是他们顺时针走，问他们期望走多远才能到达补给站？

答案是1/3公里。

用圆环很容易看出对称，用线段的话不容易说服别人中间和两头是一样的。其实都一样，看你怎么想。[吴永铮 (5-20 13:19, Long long ago)] [ 传统版 | sForum ][登录后回复]15楼