先日、 AtCoder で次のような出題があり、解けなかった。 C: Linear Approximation - AtCoder Beginner Contest 102 | AtCoder
解説 (Editorial - AtCoder Beginner Contest 102 | AtCoder) を読むと、
b を Bi の中央値にするのが最適であることがわかります
とだけ書いてあり、なんでそうなるのか分からなかった。証明を試みたけど、すぐには思いつかず、あきらめた。ところが数日後、Coursera の画像処理のコースを見ていたら、同じのような話が出てきて、驚いた。以下のコースの3週目の6個目の動画あたり。
これによって、以下の2つの性質を知ることになった。今まで知らなかったことに驚き。もしくは、学んだけど忘れたのかも。 高校の数学で出てきそうな内容ではあるけど、証明に微分使ったほうが簡単なので出てこないか? 統計力学の授業とかでも習っててもおかしくなさそう。
数列 $a_i$ と数 $b$ に対して、
\begin{equation*} \sum (a_i - b)^2 \end{equation*}を最小にする $b$ は $a_i$ の平均値となる。
これは$\sum (a_i - b)^2$を $b$ で微分して0になるという条件から出てくる。
数列 $a_i$ と数 $b$ に対して、
\begin{equation*} \sum |a_i - b| \end{equation*}を最小にする $b$ は $a_i$ のミディアンとなる。
こちらは絶対値が入っていて微分可能でない部分があるのではないかとか考えたが、 和を2つに分けてしまって微分してしまえば良いっぽい。
$a_i$ は小さい順にソートされているとしても一般性を失わないので、$i=1...m$ のとき $a_i \lt b$、$i=m+1...N$ のとき $a_i \geq b$ とすると、 \begin{equation*} \sum _{i = 1}^{N} |a_i - b| = -\sum _{i = 1}^{m} (a_i - b) + \sum _{i = m+1}^{N} (a_i - b). \end{equation*}
これを $b$ で微分して 0 になるという条件から、
\begin{equation*} m - (N -m) = 0 \Rightarrow m = \frac{N}{2}. \end{equation*}$m$ が $N$ の半分の位置にあるということは、つまり $b$ は $a_i$ のミディアン。
以上、雑な証明だと思うけど、納得した。物理学科卒なので細かいことは気にしない。こういう証明モドキですらやってみるのは何年ぶりか。。
ミディアンの方は自力では最後まで行けなかったので、適当にググって以下を見つけた。