[機統] 繩子任意切成三段 最長段期望值

[outshaker (out)]

這是以前資工上機率統計課時，教授說這題解出來就直接pass的題目。
以下是解題過程

定義問題：長度為1的繩子任意切兩刀，最長段繩子的期望值。
繩子可視為連續點構成的線段，切出的繩長可以為零。

分析：先簡化問題，變成切一刀的情形
最長可能為1，最短可能為1/2，分佈機率是均等的。
故切一刀的期望值是(最長+最短)/2 = 3/4
如果切在長度為L的繩子，最長段的期望值是(3/4)L

把原來的問題轉換成「任意切一刀之後再切第二刀」的情形討論。
令第一刀所切位置為x，產生兩段長度分別為x和1-x的繩子。
令第二刀所切位置介於x和1之間，也就是1-x的繩子上。
這部份是為了討論方便，第二刀落在0和x之間的情況，會對應到第一刀落在1-x位置的情
形。
所以這樣的假定可以考慮到全部的情形。

另外，切第一刀後，位置0到x這段繩子稱為X段。
而第二刀切下所產生的兩段繩子中最長段的長度為y，稱為Y段。

以下分成三種情況：

1. x介於0和1/3：
這種情況，Y段的最小值為(1/2)*(1-x)
Y？X → (1/2)*(1-x)？x → 1-x？2x → 1？3x → 1＞3x，必定大於X段。
是故，這種情況可以只看Y段的期望值，所以是(3/4)*(1-x)。

2. x介於1/2和1：
這種情況，Y段的最大值為1*(1-x)
Y？X → 1-x？x → 1？2x → 1＜2x，必定小於X段。
是故，這種情況可以只看X段，所以是x。

3. x介於1/3和1/2：
這種情況，Y段和X段，要討論更細微。
若Y段要大於X段，則必須
(□為Y段佔(1-x)多少比例，□正常範圍介於1/2和1之間)
Y＞X → □(1-x)＞x → □＞x/(1-x)
所以只要□大於x/(1-x)最長段就是Y段，反之則是X段。
令p=x/(1-x)
因為□是均勻分佈在1/2和1之間，所以□＞p的機率就是(1-p)/(1-1/2) ＝ 2(1-p)
□＜p的機率就是2p-1。（□＝p的機率趨近為0，可以忽略端點，只看累積的量）
採計Y段的話就要看期望值，Y段的範圍介於x到1-x之間
因為機率分佈平均，所以期望值是1/2。
所以合併起來，採計Y段的機率是2(1-p)，對應到的值是1/2
採計X段的機率是2p-1，對應到的值是x
寫成等式為2(1-p)*(1/2)+(2p-1)*x經過有點繁雜的化簡之後得到-3x+1/(1-x)
因為有點複雜，還是附上示意圖(http://ppt.cc/T-29)做參照之用。

我最後是把這三種情況用積分累加起來
From 0 to 1/3,       ∫(3/4)*(1-x)dx = 5/24
From 1/3 to 1/2,     ∫-3x+1/(1-x)dx = ln 4/3 - 5/24
From 1/2 to 1,       ∫x dx = 3/8
總和是 ln 4/3+3/8 ≒ 0.662682072

跟我用程式的隨機數字去測的結果是相近的
一開始用直覺猜是2/3（最長1，最短1/3的中間值）
可是因為機率分佈不確定是否為平均分佈。
再加上後來求解去比對，發現還是有些微差異。
原本是想如果機率分佈是均勻的話，可以一路往下推變成切n刀的通解。
不過算到這裡就知道沒希望了，還是免不了要分開討論的情形…

跟這問題奮鬥的時間很長，最近又卯起來把它算了出來，連ln都出現了
我想應該也不算簡單的題目，不知道有沒有人要挑戰切三刀的…


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.213.250
推 LimSinE     :我覺得答案是11/18，,這個答案跑出ln不大合理:::
→ simonjen    :我覺得答案是發散 (就是會無限大)
推 hectorhsu   :怎麼會是發散-         -
→ outshaker   :沒人發現我有地方筆誤…p=x/(1-x)才對…偷改回去
※ 編輯: outshaker       來自: 140.115.213.250      (05/19 12:21)
→ outshaker   :我後來調整了隨機數產生的方式，結果比較接近11/18
→ outshaker   :當初用到對稱情形，可能不小心把非對稱的狀況算進去
→ simonjen    :少乘一個dx 難怪會無限大