公開日 :
更新日 :

期待値

期待値 = 「（起こる）×（その確率）」を全部足したもの = 何度も繰り返したときの平均。
競プロで大切なのは、次の \(2\) つ。

  • 線形性 : \(E[X + Y] = E[X] + E[Y]\) （\(X\) と \(Y\) が独立でなくても成り立つ）
    → 「1個ずつの寄与」に分けて足せる。
  • 場合分け : \(E=\sum P(\)場合\() \times E[\) その場合のときの値\(]\)
    → 期待値 DP の遷移になる。

定義

\(E[X] = \sum(\)値 \(x) \times (X = x\) になる確率\()\)

例 : サイコロ \(1\)個の出目

E = 1×1/6 + 2×1/6 + 3×1/6 + 4×1/6 + 5×1/6 + 6×1/6 = 21/6 = 3.5

3.5 という目は出ないが、何回も振ったときの平均は 3.5 に近づく。
期待値は「実際に出る値」でなくてよい。

線形性

式意味
\(E[X + Y] = E[X] + E[Y]\)和の期待値は期待値の和。
独立でなくてもOK。
\(E[aX + b] = a E[X] + b\)定数倍・定数の足し算はそのまま外に出せる。
\(E[X_1 + \dots + X_n] = E[X_1] + \dots + E[X_n]\)いくつでも分けられる

例 : サイコロ \(2\) 個の出目の和 → \(3.5 + 3.5 = 7\) （\(36\) 通りを全部書き出さなくていい）

指示変数（寄与で数える）

「X ＝ 条件を満たすものの個数」は、「i 番目が条件を満たせば 1、満たさなければ 0」の和に分けられる。

E[個数] = \(\sum_i P(i\) 番目が条件を満たす \()\)

例 : \(1 \sim n\) をランダムに並べたとき、\(i\) 番目に \(i\) がある位置（不動点）の個数の期待値

  • \(i\) 番目に \(i\) が来る確率は \(\frac{1}{n}\)
  • \(n\) 個足して \(n \times \frac{1}{n} = 1\) （\(n\) によらない）

全部の並べ方（\(n!\)通り）を調べなくても、\(1\)個ずつの確率を足すだけで済む。