從自然數 1 ~ n 中隨機取 m（1≤m≤n）個，其中最大數的數學期望是多少？

12-11

兩個邊界是知道的，m=n的時候肯定是n，m=1的時候是(n+1)/2，那其他的m呢？

$frac{sum_{k=m}^nkC_{k-1}^{m-1}}{C_n^m}$

$=frac{sum_{k=m}^nkfrac{(k-1)!}{(m-1)!(k-m)!}}{C_n^m}$

$=frac{sum_{k=m}^nmfrac{k!}{m!(k-m)!}}{C_n^m}$

$=frac{msum_{k=m}^nC_k^m}{C_n^m}$

$=frac{mC_{n+1}^{m+1}}{C_n^m}$

$=frac{mfrac{(n+1)!}{(m+1)!(n-m)!}}{frac{n!}{m!(n-m)!}}$

$=frac{m(n+1)}{m+1}$

換另一個思路。

把1-n按從左到右順序排列好，然後從中抽出m個數。因為產生了m個空位，那麼剩下的數被分隔為了m+1段。（註：如果數字1被取出，那麼因為1左邊沒有數字了，所以實際上不滿m+1段，但是我們仍然認為在1左邊有一個長度為0的數欄位；如果數字n被取出，同樣認為n右邊有一個長度為0的數欄位；以及如果取出了兩個相鄰的數字，也認為這兩個數字之間夾著一個長度為0的數欄位。）
設這m+1個數欄位的長度分別為 $L_1,L_2,...,L_{m+1}$ ,由於所有數欄位長度之和為n-m，由對稱性可知： $mathbb{E}left( L_i ight) =frac{n-m}{m+1} ,quad forall i=1,2,...,m+1$
容易發現，取出的m個數字中，從小到大排第k個數字Xk滿足 $X_k=k+sum_{i=1}^{k}{L_i}$ ，所以 $mathbb{E}left( X_k ight)=k+k*frac{n-m}{m+1} =frac{k(n+1)}{m+1}$

這與 @Richard Xu和 @王某魚的結果是一致的。
-------------------------------------------------------------------------------
可能上面對稱性的表述不夠好，如果無法理解這裡的對稱性的話，可以再考慮一個等價的模型。
把m個紅球排成一行，這樣形成了m+1個空格（包括相鄰兩球之間的間隔和最左端、最右端的空地）。現在把n-m個黑球隨機放入這m+1個空格中，每個空格中的黑球數也就等價於上文中數欄位長度Li。這樣各個Li之間的對稱性應該更明顯一點。

@Richard Xu 的答案非常好，稍作小改動可以得到從小到大排第 $k$ 的數的期望是 $dfrac{(n+1)k}{m+1}$

從小到大的第 $k$ 個數 $xi$ 取 $t$ 當且僅當在 $1$ 到 $t-1$ 中取出了 $k-1$ 個數且在 $t+1$ 到 $n$ 中取出了 $m-k$ 個數.

於是 $mathbf{P}(xi=t)=dfrac{ ext{C}_{t-1}^{k-1}cdot ext{C}_{n-t}^{m-k}}{ ext{C}_n^m}$ .

(注,
這裡其實證明了對一切 $kin {1,2,3,cdots,m}$ , $sum_{t=k}^{n-m+k} ext{C}_{t-1}^{k-1}cdot ext{C}_{n-t}^{m-k}= ext{C}_n^m$ , 等一下還要用一次)

$egin{align*}mathbf{E}xi=sum_{t=k}^{n-m+k}dfrac{tcdot ext{C}_{t-1}^{k-1}cdot ext{C}_{n-t}^{m-k}}{ ext{C}_n^m}\ =sum_{t=k}^{n-m+k}dfrac{kcdot ext{C}_{t}^{k}cdot ext{C}_{n-t}^{m-k}}{ ext{C}_n^m}\ =dfrac{k}{ ext{C}_n^m}sum_{s=k+1}^{(n+1)-(m+1)+(k+1)} ext{C}_{s-1}^{(k+1)-1}cdot ext{C}_{(n+1)-s}^{(m+1)-(k+1)}\ =dfrac{k ext{C}_{n+1}^{m+1}}{ ext{C}_n^m}=dfrac{k(n+1)}{m+1}end{align*}$ .

我來給個史上最不嚴謹的解法吧。。。

首先，期望值E和n的大小應該呈線性關係(a)。從1~100之間取m個數，期望值應該是1~1000之間取m個數的1/10。E~n

其次，m越大，期望值越高。但二次導數應該是負的(b)。m越大，dE/dm越小。有不少連續增加但二次導數是負數的函數，但這題里的答案必須是有理數，所以可以排除log，sqrt。應該是E~1-1/m或者1-1/m^k之類的表達式(c)。

m=1時，期望值E=(n+1)/2。m=n-1時，期望值是n-1/n（只有1/n的可能是max=n-1，其他情況是max=n）。m=1那個邊緣條件讓E=(1-1/m)*g(n)不滿足。但E=m/(m+1)*g(n)滿足。m=n-1那個邊緣條件讓E=m/(m+1)*n不滿足，但E=m/(m+1)*(n+1)滿足。所以我猜答案是E=m/(m+1)*(n+1)，結果果然是。

這裡(a)，(b)，(c)都是小手一揮想出來的。寫答案時別這麼揮。。。

我來發一個利用數列遞推的解答