一根1米長的繩子，隨機切N刀，變成(N+1)根繩子，為什麼最短的一根繩子長度的期望是1/(N+1)^2？

01-21

隨機切N刀，指切口的位置在繩子上服從均勻分布，且相互獨立。
我用電腦模擬驗證了一下1至4刀的情況，基本準確。

想了半天，還是這樣解釋吧：

真的不需要微積分。

我們隨機選Ｎ個小繩子。小繩子長度分別為x1,x2,x3,...xN。

腦補一個Ｎ維空間。空間當中（x1,x2,x3...xN）這一組coordinates（向量、vector）都對應一個點。就是說每個小繩子組合都是這個空間當中某個獨立的點。

然後每個繩子長度都必須大於零，所以這已經把空間限制住了一些。

但是這小繩子組合有個更重要的限制，x1 + x2 + ... + xN = １。畢竟是個一米繩子被拆開。

所以我們的「點群」變成一個很有限的小區域。二維（Ｎ＝２）的話，就是一條線，三維的話（Ｎ＝３），就是一個plane。更多維，那隻能想像成一種立體區。也不會無限大。

好吧，我們想知道這個立體區的均值。那就是它這個區域的centre of mass。怎麼算出來？其實不用再腦補，畢竟是一個convex的區域，所以只要把每個邊界極端點加起來算平均即可。極點倒底是哪些？(1,0,0,0...)，(0,1,0,0...)，(0,0,1,0...) ... (0,0,0...,1)。都是這個區域的邊界點。求平均？那總共有N個，所以平均在(1/N, 1/N, 1/N...)這個點。就是說Ｎ個隨機小繩子，如果符合這個要求，平均結果是各個長度均為1/N。

這個很無聊啊。。。題主問的是最短繩子平均長度。

那我們再設定新的一堆限制：x1&>x2&>x3&>...&>xN。要求這個排序。最長的小繩子長度是x1。最短的繩子是xN。又大大限制住了我們的目標區域。

想一想，如果Ｎ=２，那x1＋x2 = 1這就是一個從(1,0)到(0,1)的一條線。突然要求x1&

OK，我們只要把這個問題再放大到更多維。三維還稍微能腦補想像。(1,0,0)，(1/2,1/2,0)，(1/3,1/3,1/3)，這三個極點。一個平面三角形。均值只需要算出來。(11/18, 5/18, 2/18)。是不是符合正式結果？是。。。把一米繩子隨機分為三塊，最長平均為11/18米，最短平均為2/18米。

－－－補充－－－

這裡可能要解釋極點怎麼算出來。。。按照上面的限制，xJ最大也只有1/J。這樣會逼著K&J的xK等於０。自然就是其中一個極點。

每個極點也都是把某個小繩子最大化。

另外，為何在這麼多限制下，centre of mass還是準的？因為本來的大區域是一個隨機平衡分布；每加一條限制，剩下的區域仍然是平衡分布。追求該區域的核心即可。

－－－

三維11:5:2，這個比例，下午在模擬統計。截個圖吧：

目前還都很符合。。。

把維度再放大，道理完全一樣。Ｎ=４，一個四維空間當中的三維區域，極點自然是(1,0,0,0)、(1/2,1/2,0,0)、(1/3,1/3,1/3,0)、(1/4,1/4,1/4,1/4)。

均值centre of mass一樣為(6/96,14/96,26/96,50/96)。也很符合統計結果。。。

目前我們發現Ｎ=２的最短繩子平均長度為１/４米。

Ｎ＝３，最短為１/９。Ｎ＝４，最短為１/１６。

如何證明任意Ｎ，最短為１/Ｎ^２呢？其實只要把這個極點平均思維堅持下去。

Ｎ個小繩子。極點就是：

(1,0,0,0...)

(1/2,1/2,0,0...)

(1/3,1/3,1/3,0...)

...

(1/N,1/N,1/N...1/N)

那麼均值永遠是：

(

1/N * (1/N)

1/N * (1/N + 1/N-1)

1/N * (1/N + 1/N-1 + 1/N-2)

...

1/N * (1/N + 1/N-1 + 1/N-2 + ... + 1/2 + 1)

)

我們不僅證明了最短小繩子的平均長度。還算出來了所有繩子的平均長度。

可以算C(N,K)，Ｎ個繩子，其中排名K-th的平均長度。

C(N,K) = 1/N * (1/N + 1/N-1 + ... 1/K)

其中最短的K=N

C(N,N) = 1/N * (1/N) = 1/N^2

其中最長的K=1

C(N,1) = 1/N * (1/N + 1/N-1 + 1/N-2 ... + 1/2 + 1)

這已經更廣泛了。而且我覺得上面的邏輯已經足以證明這個事實。雖然腦補多維空間有點難。。。核心思維還是可以延長到多個維度。

－－－

一樣也應該有辦法通過induction證明這個。因為追求C(N+1,i)，Ｎ+1個繩子，把最短的長度為K去掉，再給另外N個扣掉K，剩下的Ｎ個繩子應該符合C(N,i)的分布。從此可以得出下一個K以及整個Ｎ+1的分布。

可能還有許多方法證明，但是從他的分布的區域shape這角度應該是最直觀的，也蠻好理解。

－－－

我們另外能得出那些細節？

C(N,1)，最長繩子的的長度，在Ｎ很大的時候，應該接近1/(NlogN)。

因為 1 + 1/2 + 1/3 + 1/4 ... + 1/N　接近 logN。

C(N,1)與C(N,N)的長度比例，（最長繩子與最短的繩子的比例）應該接近N/logN。

C(N, N-1)與C(N,N)的比例應該接近2。

就是說Ｎ很大，最短繩子的平均長度接近第二短繩子長度的二分之一。

等等。。。

直觀解法無能，只好給一個使用常見分布轉換大法的暴力解法。

1. [0,1]區間均勻的選取n個點將區間分成長度依次為 $(X_1,cdots,X_{n+1})$ 的(n+1)段, 那麼

$(X_1,cdots,X_{n+1})stackrel{d.}{=}frac{(Y_1,cdots,Y_{n+1})}{(Y_1+cdots+Y_{n+1})}$ , 其中 $Y_i$ 為獨立同分布的 $mathrm{Exp}(1)$ 分布。

這一點或者從 $(X_1,cdots,X_{n+1})$ 服從參數為 $(1,dots,1)$ 的Dirichlet分布（可以想像為Beta分布的推廣），然後利用Beta/Dirichlet 分布的性質。或者把這個過程想成Poisson過程，然後利用Poisson過程的給定T時刻前有n個到達，那麼n個到達時間在[0,T]上均勻分布的性質。

於是我們的問題變成了對n+1個獨立的指數分布，求解 $min{Y_1,cdots,Y_{n+1}}/(Y_1+cdots+Y_{n+1})$ .

2. 令 $Y_{(1)}lecdotsle Y_{(n+1)}$ 為 $(Y_1,cdots,Y_{n+1})$ 的順序統計量，並令 $Z_i=Y_{(i)}-Y_{(i+1)}$ . 根據指數分布的無記憶性， $Z_isimmathrm{Exp}(n+2-i)$ 且 $Z_i$ 彼此獨立。我們有

$egin{cases} min{Y_1,cdots,Y_{n+1}}=Z_1,\ (Y_1+cdots+Y_{n+1})=(n+1)Z_1+nZ_2+cdots+Z_{n+1}. end{cases}$

於是我們所求的期望等於 $Z_1/sum_{i=1}^{n+1}(n+2-i)Z_i$ .

3.最後注意到根據指數分布的性質， $(n+2-i)Z_isimmathrm{Exp}(frac{n+2-i}{n+2-i})=mathrm{Exp}(1)$ . 所以再一次利用Beta/Dirichlet分布和指數分布之間的關係，我們有

$frac{((n+1)Z_1,nZ_2,dots,Z_{n+1})}{(n+1)Z_1+nZ_2+cdots+Z_{n+1}}$ 服從參數為 $(1,dots,1)$ 的Dirichlet分布.

所以 $mathbb{E}frac{Z_1}{sum_{i=1}^{n+1}(n+2-i)Z_i}=frac{1}{n+1}mathbb{E}frac{(n+1)Z_1}{sum_{i=1}^{n+1}(n+2-i)Z_i}=frac{1}{(n+1)^2}.$

類似的我們可以得到第k小的長度的期望等於

$mathbb{E}frac{Y_{(k)}}{Y_{(1)}+cdots+Y_{(n+1)}}=mathbb{E}frac{Z_1+Z_2+cdots+Z_k}{sum_{i=1}^{n+1}(n+2-i)Z_i}=frac{1}{(n+1)}sum_{i=n+2-k}^{n+1}frac{1}{i}.$

【搶紅包中的數學】

我想，這道題如果換種表述方法 (本質相同)，關注的人一定會翻好幾倍：

證明：有微信紅包總共 1 元，隨機發給 n 個人，則拿到錢最少的人平均可以拿到 $frac{1}{n^{2} }$ 元

這道題其實並不難，懂一點點概率，加上一點點積分知識即可。

證：

引理：不排序，當紅包共有 n 個的時候，第一個人拿到至少 x 元的概率為 $left( 1-x ight)^{n-1}$

這是容易理解的，因為，第一個人拿到至少 x 元，相當於 n-1 刀的每一刀都切在後 (1-x) 上

推論：當紅包共有 n 個的時候，每一個人至少拿到 x 元的概率為 $left( 1-nx ight)^{n-1}$

即 $P(v_{min}>x )=left( 1-nx<br /> ight)^{n-1}$

我們要求的是拿錢最少的人所拿錢數的數學期望

$E(V_{min} )=int_{0}^{1/n}v_{min}p(v_{min}) dv_{min}=int_{0}^{1/n} P(v_{min}>x )dx=int_{0}^{frac{1}{n} } left( 1-nx<br /> ight)^{n-1} dx$

$=frac{1}{n} int_{0}^{1} left( 1-nx ight)^{n-1} d(nx)=frac{1}{n} int_{0}^{1} left( 1-u ight)^{n-1} du=-frac{1}{n^{2} } left( 1-u ight)^{n}|_{0}^{1}=frac{1}{n^{2} }$

證畢！

【附】

關於 $int_{0}^{1/n}v_{min}p(v_{min}) dv_{min}=int_{0}^{1/n} P(v_{min}>x )dx$ ，

有人覺得不顯然，只好證明一下：

$int_{0}^{1/n}v_{min}p(v_{min}) dv_{min}=int_{0}^{1/n}xp(x) dx=int_{0}^{1/n}xdP(x)=xP(x)|_{0}^{1/n}- int_{0}^{1/n}P(x)dx$

$=frac{1}{n} cdot P(frac{1}{n} ) -0 cdot P(0)- int_{0}^{1/n}P(x)dx=frac{1}{n} -int_{0}^{1/n}P(x)dx=int_{0}^{1/n}(1-P(x))dx=int_{0}^{1/n} P(v_{min}>x )dx$

********************

更一般地，當紅包共有 n 個的時候，拿錢第 k 多的人拿到錢的數學期望： $E(V_{k} )=frac{1}{n}sum_{i=k}^{n}{frac{1}{i} }$

（留作習題 233333）

結論的運用：

我有 10 元，發 10 個紅包，拿錢第 k 少的人平均會拿到多少錢呢？

從少到多分別為：

0.1 元，0.21 元，0.34 元，0.48 元，0.65 元，0.85 元，1.10 元，1.43 元， 1.93 元， 2.93 元

試著答一下，假設最短的一根繩子的長度為 $x$ ，剩餘 $n$ 條繩子的長度可表示為 $x+x_1,x+x_2,...,x+x_n$ 且滿足 $forall x_igeq 0, i = 1,...,n$ ，如下圖所示：

顯然，

$x + (x + x_1) + (x + x_2) + ... + (x+x_n) = 1$

左右兩邊同時求期望，則：

$E(x_1 + x_2 + ... + x_n) = 1 - (n+1)E(x), E(x)geq 0$

如果想要知道 $Eleft( x ight)$ 的值，等價於：

在 $sum_{i=1}^{n}{x_i}leq 1$ 的條件下，計算 $E(x_1 + x_2 + ... + x_n)$ 的值，不妨將此值記為 $E_n$ ，即 $E_n = E((sum_{i=1}^{n}{x_i}|sum_{i=1}^{n}{x_i}leq 1)$

下一步，根據全期望公式 $Eleft( X ight) = E(E(X|Y))$ ，有：

$E_n=E(E(sum_{i=1}^{n}{x_i}|x_n)) =E[x_n+E(sum_{i=1}^{n-1}{x_i}|sum_{i=1}^{n-1}{x_i}leq 1-x_n)]$

由 $E_n$ 定義，可化簡上式中括弧內的部分，得到：

$E_n = E(x_n + E_{n-1}(1-x_n))=E_{n-1}+(1-E_{n-1})Ex_n$

由於我們並沒有對 $x_1,...,x_n$ 加以區分，所以有 $Ex_n = frac{1}{n} E_n$ ，代入上式可得：

$E_n = E_{n-1} + frac{1}{n} (1-E_{n-1})E_n$ ，即得到遞推公式： $frac{n-1}{E_{n-1}}= frac{n}{E_{n}}-1$ 。

觀察在 $n=1$ 時， $E(x) = frac{1}{4}$ ，則 $E_1 = 1-2 imes frac{1}{4} =frac{1}{2}$ ，即 $frac{1}{E_1}=2$ ，代入上面得到的遞推公式，可知： $frac{n}{E_n}=n+1, E_n = frac{n}{n+1}$

最終得到： $E(x) = frac{1}{(n+1)^2}$ ，證畢！

05142351更：曾加大神的解法更巧妙哇~我這個更像是考試答案。。

以下回復 @一隻粗壯的蘑菇評論提出的問題，補充一處的詳細推導過程：

$E_n$ 的定義是： $E_n = E(sum_{i=1}^{n}{x_i}|sum_{i=1}^{n}{x_i}leq 1)$

$E_{n-1}$ 的表達式可寫為 $E(sum_{i=1}^{n-1}{y_i}|sum_{i=1}^{n-1}{y_i}leq 1)$ ，此處令 ${y_i}=frac{1}{1-x_n}{x_i}$

整理可得：

$E(sum_{i=1}^{n-1}{y_i}|sum_{i=1}^{n-1}{y_i}leq 1)=frac{1}{1-x_n} E(sum_{i=1}^{n-1}{x_i}|sum_{i=1}^{n-1}{x_i}leq 1-x_n)$

故而，

$E(sum_{i=1}^{n-1}{x_i}|sum_{i=1}^{n-1}{x_i}leq 1-x_n)=(1-x_n)E_{n-1}$ ，得證。

$E=lim_{x ightarrow infty }{frac{frac{1}{x}C_{x}^{n}+ frac{1}{x}C_{x-n}^{n}+frac{1}{x}C_{x-2n}^{n}+ullet ullet ullet }{C_{x}^{n} } } =lim_{x ightarrow infty }{frac{1}{x}(1+(1-frac{n}{x})^{n}+(1-frac{2n}{x})^{n}+(1-frac{3n}{x})^{n}+ullet ullet ullet ) }=lim_{x ightarrow infty }{frac{1}{x} (1+(1-frac{n}{x})^{n}+(1-frac{n}{x})^{2n}+(1-frac{n}{x})^{3n}+ullet ullet ullet)}=lim_{x ightarrow infty }{frac{1}{x} imesfrac{1}{1-(1-frac{n}{x})^{n}}}=frac{1}{n^{2} }$

在這個頁面(英文)有關於這個問題的討論(和解答?), 答主還沒有仔細看, 大神看了可以翻譯下.

probability - Average length of the longest segment

現在開一下腦洞, 題主要求均勻分布(uniform distribution), 但小學生沒有學過概率密度函數(pdf)和微積分怎麼辦? 小學生只會做離散的概率分析(排列組合). 下面我們就來分析一下這道題的離散版:

題目: 假設有 M 個完全相同的球, 我們要把它們分成 N+1 堆 (原題切 N 刀) , 每堆有序號, 每堆可以為 0 , 那麼最小堆的球數的期望值是多少?

我們知道把 M 個球分成 N+1 堆有 $M+N choose N$ 種分法, 因為這等同於把 M 個球和 N 根棒放成一排的放法數( N 根棒隔開了 N+1 堆). 假設每種分法的概率相等.

如果要求每堆至少一球呢？有 $M+N-(N+1) choose N$ 種分法, 因為我們可以先拿走 N+1 個球, 剩下的球分成 N 堆, 然後每堆再加一個.

以此類推, 每堆至少有 i 球的分法有 $M+N-i(N+1)choose N$ 種.

所以, 令最小堆球數為 Y , 則最小堆球數的期望值為

$E_M = sum_{y=0}^{M}{y mathbb{P}(Y=y)} = sum_{y=1}^{lfloor M/(N+1) floor}{mathbb{P}(Ygeq y)}$ $= sum_{i=1}^{lfloor M/(N+1) floor}{frac{inom{M+N-i(N+1)}{N}}{inom{M+N}{N}}}$ (*)

OK!我不知道怎麼簡化, 但是我們有計算機:-). 用計算機我們可以發現(可以自己試下):

結果: $lim _{M ightarrow infty }{frac{E_M}{M}} = frac{1}{(N+1)^2}$

看上去不錯! 我們用離散的方法估計了所求的值, 並且好像很准

現在還差兩個問題:

1) 證明 (*)/M 會趨向於 1/(N+1)^2 (希望)

2) 證明我們用離散的估計方法取得的值與連續時的值的差會任意小, 只要 M 足夠大

第二個不難證, 我有空寫. 第一個求大神幫忙! 【樓上已經給出正解, 我這個就當數學分析的習題吧...... 】

我們成功的把一個積分問題轉化為了一個級數問題! 不過小學生好像還是不會做 :"-(

這段論述雖不嚴格，也是一個思路：

令 X_1, X_2,..., X_n 為 [0, 1] 均勻分布，X_(1) &< X_(2) &< ... &< X_(n)為其順序統計量。

則 Y_1 = X_(1), Y_k = X_(k) - X_(k-1), k = 2, ..., n, Y_n+1 = 1 - X_(n) 為繩子長度。

考慮 n -&> inf 的極限情況。

P{nX_(1) &> t} = P{X_(1) &> t/n} = (1-t/n)^n -&> exp(-t) 即 Exp(1) = Gamma(1,1) 。

P{nX_(2) &> t} = P{nX_(1) &> t} + P{nX_(1) &< t, nX_(2) &> t} = (1-t/n)^n + n(t/n)(1-t/n)^(n-1) -&> exp(-t) + texp(-t) 即 Gamma(2,1)。

可見 nX_(k) -&> Gamma(k,1)。另一方面，Gamma(k,1) 是 k 個 i.i.d. 指數分布之和，而 X_(k) = Y_1 + ... + Y_k。大膽猜測，極限情況下，Y_# 接近 i.i.d. 指數分布。由於 n+1 個 Y_# 之和為1，認為 Y_# ~ Exp(n+1)。

把繩子長度排序：Y_(1) &< Y_(2) &< ... &< Y_(n) &< Y_(n+1)。

E[Y_(k)] = E[Y_(1)] + E[Y_(2)-Y_(1)] + ... + E[Y_(k)-Y_(k-1)] = 1/(n+1) [ 1/(n+1) + ... + 1/(n+2-k)]。

Reference: Feller.