AHC で出てくる分布 - Kiri8128の日記

AHC でよく出てくる分布について書きます。

（書きかけ。あとで追記する。）

確率分布と確率変数

あとで書く。

期待値と分散

確率変数 $X$ の期待値を $E(X)$ 、分散を $V(X)$ と書きます *1 。

正規分布

こんなやつ。

確率変数 $X$ が平均 $\mu$ 、分散 $\sigma ^{2}$ の正規分布に従うとき $X \sim N(\mu, \sigma^{2})$ *2 と書きます。

特徴

あとで書く

対数正規分布

$X \sim N(\mu, \sigma^{2})$ のとき、 $Y=e^X$ が従う分布を対数正規分布と言い、 $Y \sim \Lambda(\mu, \sigma ^{2})$ と書きます。

特徴

このとき $E(Y)=e^{\mu+\frac{\sigma ^{2}}{2}}$ が成立します。

お気持ち

$X$ の平均が $\mu$ なんだから $Y=2^{X}$ の平均は $e^{\mu}$ なんじゃないかと思いがちですが、それよりは分散がある分だけ若干大きくなります。

例えば $X$ が $-1$ 、 $0$ 、 $1$ の値を等確率で取る確率変数だとすると、 $2^{X}$ は $\displaystyle\frac{1}{2}$ 、 $1$ 、 $2$ となり、平均は $\displaystyle\frac{7}{6}$ なので $1$ を若干超えますね。

例

AHC029 では、プロジェクトの残務量および価値や、方針カードの労働力およびコストが対数正規分布 *3 になっていました。

プロジェクトの生成

このように生成されます。

何やらややこしい数式が書かれているように見えますが、 round と clamp を無視すれば *4 、大したことはないですね。

このとき、プロジェクトの価値を残務量で割った比率の期待値がどれぐらいになるか気になりませんか？ほぼ同水準に近いように作られているように見えますが、平均は $1$ ではありません。

round 関数と clamp 関数を無視すれば、 $\displaystyle\frac{v}{h}$ は $\displaystyle\frac{2^{\mathrm{gauss}(b,\ 0.5)}}{2^{b}}$ の部分、つまり上の記法で $\Lambda (0, 0.5^{2})$ の対数正規分布になっています。底が $2$ であることに注意すると、これは $\Lambda(0, (0.5 \log 2)^{2})$ に従います。よってこの期待値は $\displaystyle\frac{(\log 2)^2}{8} \fallingdotseq 1.061896 \cdots$ であると分かり、価値の期待値は初期残務量より $6.2\%$ 程度大きくなることが分かります *5 。