はじめに
この記事は，@aplysia さんの記事[2]
を読んでいて，躓いた部分の補足です．
自分用に書いたメモですが，せっかくなのでQiitaにあげてみました．
初投稿なので，使い方とかよく分かりません．内容が間違っている可能性もあります．
問題があればご指摘よろしくお願いします．
前提
要素数が $k$ の集合 $S$ について，真の埋蔵量の総和が $v(S)$ ，占いによって得られた値が $x$ の時，尤度 $L$ を求めたい．
問題文[1] より，$x$ は
- 平均 $\mu = (k - v(S))\epsilon + v(S)(1 - \epsilon)$
- 分散 $\sigma^2 = k\epsilon(1 - \epsilon)$
の正規分布 $N(\mu, \sigma^2)$ からサンプリングされた値を $x_0$ として，
$x = \max(0, \text{round}(x_0))$ が得られる．
累積分布関数 (Cumulative Distribution Function; CDF)
確率密度関数を $f$ とすると
CDF(x) := $\int_{-\infty}^{x} f(t) dt$
x以下，(-inf, x] の値が得られる確率．
prob_in_range(l, r) := CDF(r) - CDF(l)
(l, r] の値が得られる確率．
参考：[3]
尤度(Likelihood)の実装部分
ここから分からなかった所．
@aplysia さんの記事では，
尤度 $L$ は，正規分布 $N(\mu, \sigma^2)$ の
prob_in_range(x-0.5, x+0.5)になります．ただし，$x=0$の場合はprob_in_range(-inf, x+0.5)になります．
とあるが，
なんで $\pm 0.5$ なのか，なんで $-\infty$ なのかが分からない．
Q1. なんで $\pm 0.5$ なのか
前提 より，$x_0$ は round() によって四捨五入される．
| $x_0$ | $x$ | |
|---|---|---|
| 0 | 0 | |
| 0.4 | 0 | |
| 0.5 | 1 | < |
| 0.6 | 1 | < |
| 1 | 1 | < |
| 1.4 | 1 | < |
| 1.5 | 2 |
という感じで，例えば $x=1$ が得られた時に考えられる $x_0$ は $[1-0.5, 1+0.5)$ である.
つまり，占いで得られた値 $x$ に対して，ありえる元の値 $x_0$ は $[x-0.5, x+0.5)$ の範囲に存在する．
Q2. なんで $-\infty$ なのか
前提 より，$x_0$ は round() されたあと，さらに $0$ とmax を取る．
例えば， $x_0 = -998244353$ とか，$x_0 = -1$ とか，$x_0 = 0$ が全部 $x=\max(0, x_0)=0$ になる．
つまり，占いで得られた値 $x = 0$ の場合，ありえる元の値 $x_0$ は $(-\infty, x+0.5)$ の範囲に存在する．
Q3. なんで半開区間が逆なのか
前提 より，prob_in_range(l, r) は 区間 (l, r] の値が得られる確率を表す．
なのに，実装例で prob_in_range() に渡す引数は [l, r) とか (l, r)．
てりーさんとか，wata さんの提出コードを読んでみても同じ．
？？？
ヒントを求めて，大昔に使っていた教科書[4] を漁ってみると，
確率密度 $p(x)$ に従って発生したデータ $x_1$ に対して，$p(x_1)$ は $x_1$ が発生する確率ではない．$x_1$ が発生する確率は $0$ である．なぜなら，特定の値は幅 $0$ の区間であり，そこでの積分値が常に $0$ になるからである． $p(x_1)$ を $x_1$ の尤度と呼んで区別するのは一つには，このためである． (p.136)
との記述があった．
なるほど，つまり，正規分布のような連続確率分布では，[l, r) も (l, r] も [l, r] も (l, r) も変わらんということか．
おわりに
学校で一応習ったものの，テストでなんとなく解いて終わっていたベイズの定理と少し仲良くなれた気がします．
きっかけを作ってくださった @aplysia さん，ありがとうございました．
それから，いつも面白い問題を作問してくださる wata_admin さん，ありがとうございます．AHCが楽しくて，私生活が終わっています．
参考文献
- [1] https://atcoder.jp/contests/ahc030/tasks/ahc030_a
- [2] https://qiita.com/aplysia/items/c3f2111110ac5043710a
- [3] https://mathlandscape.com/distrib-func
- [4] 金谷健一, これなら分かる最適化数学, 共立出版, 2005, https://www.kyoritsu-pub.co.jp/book/b10010407.html.