Re: [機統] 1-100任選n數的平均絕對值差？

[LPH66 (信じる力 奇跡起こすこと)]

※ 引述《HeterCompute (異質運算)》之銘言：
: 1-100之中任選n數不重複，將其排序之後，
: 由大到小依序取其差，請問差的平均為何？
: ex:取3數1 55 99，那其差為44 54，平均就是49

: → XII         : (100-n)/(n-1)                                     03/06 09:58
: → XII         : 上面筆誤,應該是 (100-n)/(n+1)+1=101/(n+1)         03/06 10:00
: → HeterCompute: 可以說一下怎麼思考的嗎，和我算的一樣，但我是sigm  03/06 10:12
: → HeterCompute: a算很久求的                                       03/06 10:12
: 推 LPH66       : 考慮 n 紅 100-n 白的排列, 紅球即為所選            03/06 11:45
: → LPH66       : 所求為平均被紅球切開的白球長度 +1                 03/06 11:46
: → LPH66       : 一共 100-n 球被切成 n+1 段                        03/06 11:46
: → LPH66       : 由此即得此算式                                    03/06 11:47
: → HeterCompute: 感謝                                              03/06 12:18
: 推 cutekid     : 推 L 大解釋。上面的例子，應該是 (44+44)/2=44      03/06 14:45
: → yyc2008     : 看不太懂,可以請L大再詳述一下嗎?我只知道最大數-最  03/06 16:09
: → yyc2008     : 小數的所有情況的平均,不懂為何可轉換為紅切白長度   03/06 16:10
: → yyc2008     : 兩紅球之間的白球數就是一種差                      03/06 16:12
: 推 LPH66       : 連續所選兩數差 = 對應紅球位置差 = 其所夾白球數+1  03/06 17:51
: → LPH66       : 所以每個差就是一段連續白球, 所求是 n-1 段的平均   03/06 17:51
: → LPH66       : 那因為這 n+1 段白球每段都不比別段特別             03/06 17:53
: → LPH66       : 所以這平均就是連續白球長度平均 = (100-n)/(n+1)    03/06 17:53
: → LPH66       : (再 +1 補償種樹問題端點相減與間隔數的差)          03/06 17:54
: 推 yyc2008     : 謝謝LP大，很清楚，我了解了                        03/09 01:17
: → ColacoToT   : 為何結果會是只跟n有關啊？說來跟ex結果不同了吧？   03/09 15:51
: → HeterCompute: 題目要的是平均，我只是隨便舉例，當然不同          03/09 19:20
: → ColacoToT   : 題目與舉例不是只有n未知已知的差別嗎？             03/09 21:06
: → HeterCompute: 應該說題目要的是平均的"期望值"，這樣就沒爭議了    03/09 22:38
: → ColacoToT   : 那還是有個問題，L大的敘述是得n+1段平均嗎？        03/10 14:54
: → ColacoToT   : 請問為何不是n-1段？n個數的差應該只有n-1個吧？     03/10 14:54
: → HeterCompute: 因為n-1段沒辦法直接求，但是除了考慮n-1段以外的頭  03/10 16:53
: → HeterCompute: 和尾變成n+1段時不失一般性(可以想一下為什麼)       03/10 16:54
我用一點數學語言重述這個做法

令 n+1 個隨機變數 X0, X1, ..., Xn 表示選出的 n 個數加上 0, 101 共 n+2 個數

照樣排好再做相鄰數差依序得到的 n+1 個差

容易知道

(1) X0 + X1 + ... + Xn = 101  這應該沒什麼問題

    一點題外話是這裡直接考慮差就不會碰到用球考慮時的種樹問題差 1 的問題了

    也就是說, n+1 段白球其實是 X0 - 1, X1 - 1, ..., Xn - 1 個球

    白球總數是 100-n 所以除完之後才要再加 1

(2) X0, X1, ..., Xn 這 n+1 個隨機變數的分布相同

    這即是「每一段都不比別段更特別」的意思

    也是上面推文的「考慮 ... n+1 段時不失一般性」的意思

    注意到這只是單個隨機變數的分布相同而已, 它們之間並不是獨立的

    證明的提示: 可以嘗試證明對固定的 k, 所有 Xi = k 的組合都能一一對應

                這一點用球想會比較容易看得出來

從這裡容易得到 E(X0) = E(X1) = ... = E(Xn) = 101/(n+1)

而原題要求的是 E(Y), 其中 Y = (X1+X2+...+X{n-1})/(n-1)

那由期望值的線性即知 E(Y) 也會等於 101/(n+1)

所以推文在問除以 n-1 去哪裡了, 它在這裡, 和 n-1 個相同的值抵消了

====

這個分布其實是可以寫出來的:

P(Xi = k) = C(100-k,n-1)/C(100,n)

直接從這裡求期望值大概就是原 PO 一開始說的用一堆Σ去算的過程

這樣因為要在一堆二項式係數裡面算會比較吃力沒錯

====

至於後來延伸的 n-1 個差的中位數期望值和標準差期望值

這應該就要考慮到這 n+1 個隨機變數的聯合分布了

不過初看起來似乎並不好求的樣子...

--
Ace Snake Santa Clover Junpei June Seven Lotus 9th man  cabin  kitchen  casino
shower operating room laboratory  Ｔ  Ｈ  Ｅ chart captain quarter confinement
torture room steam engine room cargo chapel library study incinerator Gigantic
Q director office security  Ｎ  Ｏ  Ｎ  Ａ  Ｒ  Ｙ archives control laboratory
pec treatment garden pantry gaulem bay rec room crew quarters infirmary lounge
elevator Tenmyouji Quark Dio  Ｇ  Ａ  Ｍ  Ｅ  Ｓ Luna Phi Sigma Alice Clover K

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.174.68 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1583923683.A.381.html
推 HeterCompute: 感謝解釋，後來中位數的期望值我有用計算機幫我硬解
→ HeterCompute: 要列出公式解應該不太實際
→ HeterCompute: 標準差後來因為我覺得不是常態分佈的話，數字算出來
→ HeterCompute: 也無法說出什麼意義，我就放棄了，不過感覺應該用
→ HeterCompute: sigma硬解也行
推 Vulpix      : 中位數的公式應該是沒救的。不過我想近似值應該還是
→ Vulpix      : 在 100/n 附近吧。然後平均的期望值那邊，雖說是一
→ Vulpix      : 堆Σ，但其實兩層就夠，而且滿快的。
→ Vulpix      :   C(99,n-1)*1+C(98,n-1)*2+...+C(n-1,n-1)*(101-n)
→ Vulpix      : = C(100,n)+C(99,n)+...+C(n,n) = C(101,n+1)
→ Vulpix      : 只用到 C(100,n)+C(99,n)+...+C(n,n) = C(101,n+1)
→ Vulpix      : 這種公式。