{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 数列の平均とミディアンについて\n", "\n", "先日、 AtCoder で次のような出題があり、解けなかった。 [C: Linear Approximation - AtCoder Beginner Contest 102 | AtCoder](https://abc102.contest.atcoder.jp/tasks/arc100_a) \n", "\n", "解説 ([Editorial - AtCoder Beginner Contest 102 | AtCoder](https://abc102.contest.atcoder.jp/editorial)) を読むと、\n", "\n", "> b を Bi の中央値にするのが最適であることがわかります\n", "\n", "とだけ書いてあり、なんでそうなるのか分からなかった。証明を試みたけど、すぐには思いつかず、あきらめた。ところが数日後、Coursera の画像処理のコースを見ていたら、同じのような話が出てきて、驚いた。以下のコースの3週目の6個目の動画あたり。\n", "\n", "[Image and Video Processing: From Mars to Hollywood with a Stop at the Hospital - Duke University | Coursera](https://www.coursera.org/learn/image-processing/home/info)\n", "\n", "これによって、以下の2つの性質を知ることになった。今まで知らなかったことに驚き。もしくは、学んだけど忘れたのかも。 高校の数学で出てきそうな内容ではあるけど、証明に微分使ったほうが簡単なので出てこないか? 統計力学の授業とかでも習っててもおかしくなさそう。\n", "\n", "## 性質1\n", "\n", "数列 $a_i$ と数 $b$ に対して、\n", "\n", "\\begin{equation*}\n", "\\sum (a_i - b)^2\n", "\\end{equation*}\n", "\n", "を最小にする $b$ は $a_i$ の平均値となる。\n", "\n", "これは$\\sum (a_i - b)^2$を $b$ で微分して0になるという条件から出てくる。\n", "\n", "## 性質2\n", "\n", "数列 $a_i$ と数 $b$ に対して、\n", "\n", "\\begin{equation*}\n", "\\sum |a_i - b|\n", "\\end{equation*}\n", "\n", "を最小にする $b$ は $a_i$ のミディアンとなる。\n", "\n", "こちらは絶対値が入っていて微分可能でない部分があるのではないかとか考えたが、 和を2つに分けてしまって微分してしまえば良いっぽい。\n", "\n", "$a_i$ は小さい順にソートされているとしても一般性を失わないので、$i=1...m$ のとき $a_i \\lt b$、$i=m+1...N$ のとき $a_i \\geq b$ とすると、\n", "\\begin{equation*}\n", "\\sum _{i = 1}^{N} |a_i - b| = -\\sum _{i = 1}^{m} (a_i - b) + \\sum _{i = m+1}^{N} (a_i - b).\n", "\\end{equation*}\n", "\n", "これを $b$ で微分して 0 になるという条件から、\n", "\n", "\\begin{equation*}\n", "m - (N -m) = 0 \\Rightarrow m = \\frac{N}{2}.\n", "\\end{equation*}\n", "\n", "$m$ が $N$ の半分の位置にあるということは、つまり $b$ は $a_i$ のミディアン。\n", "\n", "以上、雑な証明だと思うけど、納得した。物理学科卒なので細かいことは気にしない。こういう証明モドキですらやってみるのは何年ぶりか。。\n", "\n", "## 参考文献\n", "\n", "ミディアンの方は自力では最後まで行けなかったので、適当にググって以下を見つけた。\n", "\n", "- \n", " - $\\sum |a_i - b|$ の式は絶対偏差和というらしい。\n", "- \n", " - $\\sum (a_i - b)^2$ は平方偏差和というらしい。\n", " - p. 90 で微分を使わずに平方偏差和を最小にするのが平均値であることを証明している。\n", "- [leeswijzers stamboom - 偏差平方和・偏差絶対値和・シュタイナー問題](http://leeswijzer.tumblr.com/post/25267757591/%E5%81%8F%E5%B7%AE%E5%B9%B3%E6%96%B9%E5%92%8C%E5%81%8F%E5%B7%AE%E7%B5%B6%E5%AF%BE%E5%80%A4%E5%92%8C%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%8A%E3%83%BC%E5%95%8F%E9%A1%8C)\n", " - これのより一般的な場合はシュタイナー問題というらしい。（全然わからん）\n", "\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.3" } }, "nbformat": 4, "nbformat_minor": 2 }