Re: [請益] 有沒有人記得

[zhixiangJ (仍然~有可能)]

※ 引述《west1996 (焦了六年變脆了)》之銘言：
: sum |Xi-a|  最小值發生在 a=median{Xi} 要怎麼證？
:  i
: 我要離散型版本的~
: 會的阿龍請吃韓江!!

  最小值的解不唯一唷  median 只是其中一個解
  可以作為高中數學歸納法的題目
  先給的 Lemma

  Lemma: Suppose X < Y and f(c) = |X-c| + |Y-c|, then we have
         f(c) >= f(m) for all m with X <= m <= Y and for all c in R
         (在 X 跟 Y 中間的值都是最小值的解)
  Proof: 略... 太容易了

  開始數學歸納法

  n = 1 時，顯然成立
  n = 2 時，按照 Lemma 中位數顯然是一個最小值的解

  假設 n = k, n = k + 1 時都成立

  當 n = k + 2 時

  符號採用排序好的 X_(1) <= X_(2) <= ... <= X_(k+1) <= X_(k+2)

  先不考慮最大值和最小值，從 X_(2) 到 X_(k+1) 共有 k 個

  令 g(c) = |X_(2) - c| + ... + |X_(k+1) - c|, a = median{Xi; 2 <= i <= k+1}

  由歸納假設 (n=k) X_(2) ~ X_(k+1) 的中位數是最小解，即

             g(c) >= g(a) for all c in R    --- (1)

  令 f(c) = |X_(1) - c| + |X_(k+2) - c|

  顯然  X_(1) < a < X_(k+2)  利用 Lemma 可得

             f(c) >= f(a) for all c in R    --- (2)

  (1) + (2) 可得

  sum |Xi-c| = g(c) + f(c) >= g(a) + f(a) for all c in R

  故 a 是最小值的一個解

  注意到 a = median{Xi; 2 <= i <= k+1} = median{Xi; 1 <= i <= k+2}

  補充：在證明中，似乎沒用到歸納假設 n = k+1 部分，
        但事實上 X_(1) 和 X_(k+2) 的 "存在性" 是必須，
        這部份就有用到 n = k+1 ，懶得寫的很完整，意思大概是這樣



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.196.42
推 west1996:感覺怪怪的，一開始的lemma只有說m在X,Y之間，這個說法好
→ west1996:像不完全等價於取X,Y,Z的median，但是如果把一開始的
→ west1996:lemma的m改成定義為X,Y的median的話還會有另外一個問題，
→ west1996:就是(1)跟(2)取出來的a也不保證是一樣的一個，這樣沒法合
→ west1996:併，再者，median如果定義成一個區間中的值都可以的話顯
→ west1996:然不可能具有加總最小這個結果，要加總最小一定是要取概
→ west1996:念上的那個中點才行吧，所以真的有取法不唯一嗎？？
1. 以 Lemma 舉例來說：假設 X=1, Y=3, 則 f(c) = |1-c| + |3-c|
   只要 1<=c<=3 , 就有 f(c) = c-1 + 3-c = 2 是最小值
   中位數 "2" 只是其中一個解。

2. Lemma 只用兩個數 (X,Y)，而不用三個數 (X,Y,Z) 是為後面的歸納法作準備的
   Lemma 說的是 n = 2 的情況，所有最小值的範圍，中位數只是其中一個解

3. 中位數有個特徵：將數列 (個數必須大於3; n>=3) 中的最大值和最小值同時抽去，
                   其中位數不變，也是就說
    a = median{Xi; 2 <= i <= k+1} = median{Xi; 1 <= i <= k+2}

   可由中位數的定義證明，證明略


4. 歸納法中的 a 是被固定的，並沒有重取的問題，一開始 a 就被定義為

    a = median{Xi; 2 <= i <= k+1} 

   這個 a 符合歸納假設，故有 (1)
   同時 a 也符合X_(1) < a < X_(k+2)，故可引用 Lemma，故有 (2)
   注意！我並沒有說 a 是 X_(1) 和 X_(k+2) 的中位數
   事實上 a 沒有必要是 X_(1) 和 X_(k+2) 的中位數，Lemma一樣可使用
   這就是我 Lemma 為什麼要那樣寫的原因，
   這樣即使 a 不是 X_(1) 和 X_(k+2) 的中位數，亦會有 (2)

5. 可以一步一步來思考

   n = 1： |X_(1)-c| 之最小值解是 a = X_(1) 中位數
   n = 2： |X_(1)-c| + |X_(2)-c| 其中一個最小值解是中位數

   n = 3： |X_(1)-c| + |X_(2)-c| + |X_(3)-c|
           先不看最小值 X_(1) 和最大值 X_(3)
           按照 n=1， X_(2)的中位數 a 是  |X_(2)-c| 最小值的解
           同時這個 a 可引用 Lemma，亦是 |X_(1)-c| + |X_(3)-c| 最小值的解
           故 |X_(1)-c| + |X_(2)-c| + |X_(3)-c| 其中一個最小值解是 a
           最後利用中位數的性質，a 亦是 X_(1) ~ X_(3) 的中位數

   n = 4, 5, 6....
           不斷重覆上面步驟
           步驟 1： 將原本數列拿去最大值和最小值，定義 a 是新數列的中位數
           步驟 2： 利用歸納假設，a 是新數列的最小值之解
           步驟 3： a 與最大值和最小值的關係滿足 Lemma，可使用 Lemma
           步驟 4： 由步驟 2 和步驟 3 ，可知 a 是原數列的最小值之解
           步驟 5： 最後說明 a 其實也是原數列的中位數

※ 編輯: zhixiangJ       來自: 118.169.192.37       (03/27 08:06)
推 superyow:P(X<=median)>=0.5 & P(X>=median)>=0.5
→ superyow:以統計上定義的中位數..離散型的會有無限多個中位數
→ zhixiangJ:嗯~這是比較廣義的定義方式
→ zhixiangJ:對了！ 順便問有沒有人要參加校友會呀?
推 superyow:阿離不達要回去演講阿....
推 yalibuda:有讀有推...
推 yalibuda:我應該會回去看看，知心不一起回去嗎？
推 kiekiekie:阿離不達有演講才去
推 west1996:請向阿龍領取韓江消費券一張
推 zlyeah:等我向west1996申請下來之後就可以找我拿了
推 west1996:記得上請購單
推 superyow:高手都請購結報一起來的....
→ zhixiangJ:哈~  有沒有認真要約吃呀？  很久沒吃了說
推 west1996:我是認真的想吃韓江...