数列の平均とミディアンについて

前回の日記で始める宣言した競プロですが、あまり上達してないけど、AtCoder だけ継続してます。

先日、 AtCoder で次のような出題があり、解けなかった。 C: Linear Approximation - AtCoder Beginner Contest 102 | AtCoder

解説 (Editorial - AtCoder Beginner Contest 102 | AtCoder) を読むと、

b を Bi の中央値にするのが最適であることがわかります

とだけ書いてあり、なんでそうなるのか分からなかった。証明を試みたけど、すぐには思いつかず、あきらめた。ところが数日後、Coursera の画像処理のコースを見ていたら、同じような話が出てきて、驚いた。以下のコースの3週目の6個目の動画あたり。

Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital - Duke University | Coursera

これによって、以下の2つの性質を知ることになった。今まで知らなかったことに驚き。もしくは、学んだけど忘れたのかも。 高校の数学で出てきそうな内容ではあるけど、証明に微分使ったほうが簡単なので出てこないか? 統計力学の授業とかでも習っててもおかしくなさそう。

性質1

数列 {a_i} と数 {b} に対して、

{ \sum (a_i - b)^{2} }

を最小にする {b}{a_i} の平均値となる。

これは{\sum (a_i - b)^{2}}{b}微分して0になるという条件から出てくる。

性質2

数列 {a_i} と数 {b} に対して、

{
\sum |a_i - b|
}

を最小にする {b}{a_i} のミディアンとなる。

こちらは絶対値が入っていて微分可能でない部分があるのではないかとか考えたが、 和を2つに分けてしまって微分してしまえば良いっぽい。

{a_i} は小さい順にソートされているとしても一般性を失わないので、{i=1...m} のとき {a_i \lt b}{i=m+1...N} のとき {a_i \geq b} とすると、

{
\sum _{i = 1}^{N} |a_i - b| = -\sum _{i = 1}^{m} (a_i - b) + \sum _{i = m+1}^{N} (a_i - b).
}

これを {b}微分して 0 になるという条件から、

{
m - (N -m) = 0 \Rightarrow m = \frac{N}{2}.
}

{m}{N} の半分の位置にあるということは、つまり {b}{a_i} のミディアン。

以上、雑な証明だと思うけど、納得した。物理学科卒なので細かいことは気にしない。こういう証明モドキですらやってみるのは何年ぶりか。。

参考文献

ミディアンの方は自力では最後まで行けなかったので、適当にググって以下を見つけた。

Jupyter で書いてからブログに転載したけどはてなTeX の書き方がめんどうなのでもうやらない。 http://nbviewer.jupyter.org/github/pn11/benkyokai/blob/master/statistics/mean_and_median.ipynb