ABC226 H - Random Kth Max
解説動画で分からなかったところを、あとから理解したのでメモ。
① 「ｋ番目の値がｘ以上」⇔「ｘ以上の値がｋ個以上」
これはあとから考えてみれば当たり前だった。
ある数列を大きい順に並べる。このとき、ｋ番目の数をｘ以上にしたい。
それには、ｘ以上の数をｋ個以上作れば良い。
ということだった。
② 「確率変数が
以上になる確率を求める関数
」を積分すると期待値が求まる
を「結果が
以上になる確率」としたときに、期待値は
を積分することによって求まる。図で表すと以下の通り。
このことを離散値の場合を例にとって、直感的に理解したい。
以下のような、確率が均一でないサイコロがあるとする。
これに「以上が出る確率
」の欄を加えると次のようになる。
は上段を右から累積和にしたものになる。そして、この
を図で表すと以下のようになる（縦軸の１目盛りは
）。
このとき、例えば（左から４番目の棒）について考えてみる。棒の高さが表しているのは「4以上になる確率」だ。では
「4になる確率」は？
というと、「(4以上になる確率)－(5以上になる確率)」なので、この部分になる。
ところで、
期待値は「A ✕ (Aになる確率)」の和
で求められる。図の中で「4 ✕ (4になる確率)」が表すものは、以下の部分の面積になる。
これを残りの目についても考えると
このようになる。よって「A ✕ (Aになる確率)」の和、つまり
期待値はグラフの面積になる！
ここから、積分の解説でお馴染みのように棒の幅を限りなく細くしていけば、が連続な関数の場合に置き換えることができる。ちなみに
のことを累積分布関数というらしい。
